TimeLimit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768K (Java/Others)Total Submission(s): 7092 Accepted Submission(s): 2417
ProblemDescription
Since 1945, when the first nuclear bomb was exploded by the Manhattan Projectteam in the US, the number of nuclear weapons have soared across the globe.Nowadays,the crazy boy in FZU named AekdyCoin possesses some nuclear weaponsand wanna destroy our world. Fortunately, our mysterious spy-net has gotten hisplan. Now, we need to stop it.But the arduous task is obviously not easy. First of all, we know that theoperating system of the nuclear weapon consists of some connected electricstations, which forms a huge and complex electric network. Every electricstation has its power value. To start the nuclear weapon, it must cost half ofthe electric network's power. So first of all, we need to make more than halfof the power diasbled. Our tanks are ready for our action in the base(ID is 0),and we must drive them on the road. As for a electric station, we control themif and only if our tanks stop there. 1 unit distance costs 1 unit oil. And wehave enough tanks to use.Now our commander wants to know the minimal oil cost in this action.
Input
The first line of the input contains asingle integer T, specifying the number of testcase in the file.For each case, first line is the integer n(1<= n<= 100), m(1<= m<=10000), specifying the number of the stations(the IDs are 1,2,3...n), and thenumber of the roads between the station(bi-direction).Then m lines follow, each line is interger st(0<= st<= n), ed(0<=ed<= n), dis(0<= dis<= 100), specifying the start point, end point,and the distance between.Then n lines follow, each line is a interger pow(1<= pow<= 100),specifying the electric station's power by ID order.
Output
The minimal oil cost in this action.If not exist print "impossible"(without quotes).
SampleInput
2
2 3
0 2 9
2 1 3
1 0 2
1
3
2 1
2 1 3
1
3
SampleOutput
5
impossible
Author
Lost@HDU
Source
HDOJMonthly Contest – 2010.03.06
Recommend
lcy
算法分析：
题意：
0~n个点，坦克都在0点（无限量，保证起点只有一个），每个点都有权值，保证坦克到达的所有点的权值和大于一半，求路径花费最少。
第一步，最短路，求出0到1~n点的最短距离。
第二步，01背包，01背包的最大容量是所有的最短路的总和（最多就是全部走完）。
代码实现：
#include<bits/stdc++.h> #define INF 0x3f7f7f7f7f7f7f7f using namespace std; long long int mp[105][105],dp[2000005]; int main() { long long int T,t=0; scanf("%lld",&T); while(T--) { for (int i=0;i<=105;i++) for(int j=0;j<=105;j++) mp[i][j]=INF;//初始化 long long n,m; scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { long long a,b,c; scanf("%lld%lld%lld",&a,&b,&c); mp[a][b]=mp[b][a]=min(c,mp[a][b]); } long long sum=0, p[105]; for(int i=1;i<=n;i++) { mp[i][i]=0; scanf("%lld",&p[i]); sum+=p[i]; } mp[0][0]=0; /*floyed最短路*/ for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { if(i!=k&&j!=i&&j!=k&&mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; } long long v=0; for(int i=1;i<=n;i++) { if(mp[0][i]<INF) v+=mp[0][i];//背包的最大容量，所有最短路的总和 } /*01背包*/ for(int i=0;i<=2000005;i++)//不知道为什么，dp数组的初始化必须放在这里，如果在上面，dp的值就很大。 dp[i]=0; for(int i=1;i<=n;i++) for(long long j=v;j>=mp[0][i];j--) { dp[j]=max(dp[j],dp[j-mp[0][i]]+p[i]); } long long ans=INF; for(int i=0;i<=v;i++) { if(dp[i]>=(sum/2+1)) { ans=i; break; } } if(ans!=INF) printf("%lld\n",ans); else printf("impossible\n"); } return 0; }
