题目链接:
http://acm.hdu.edu.cn/showPRoblem.php?pid=3339
题意:
给你一个图，每个点都有权值，然后让你派出多辆坦克，破环至少占权值一半的城市，派出坦克的代价就是从0点到那些城市的距离
求最少代价
题解:
点数很少，注意有重边
跑一发flyod，然后背包dp
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 100+10;
int d[maxn][maxn],d1[maxn],dp[11000],power[maxn];
int main(){
int T = read();
while(T--){
int n,m;scanf("%d%d",&n,&m);
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
d[i][j] = INF;
for(int i=0; i<m; i++){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
d[u][v] = d[v][u] = min(d[u][v],w);
}
ll aim = 0;
for(int i=1; i<=n; i++){
power[i] = read();
aim += power[i];
}
for(int k=0; k<=n; k++)
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
ll sum = 0;
for(int i=0; i<=n; i++)
if(d[0][i] < INF)
sum += d[0][i];
MS(dp);
for(int i=1; i<=n; i++)
for(int j=sum; j>=d[0][i]; j--)
dp[j] = max(dp[j],dp[j-d[0][i]]+power[i]);
ll ans = INF;
for(int i=0; i<=sum; i++)
if(dp[i]>=(aim/2+1)){
ans = i;
break;
}
if(ans == INF)
cout << "impossible\n";
else
cout << ans << endl;
}
return 0;
}
