题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3339
大致题意是说：有n个电站，每个电站都有一定的电量，电站之间有一定距离，我们要从0点出发去占领一些电站，使得占领的电站电量之和超过总电量的一半，求达到条件所要走的最短距离。如果可能的话，输出距离，否则输出不可能。
思路：我们从0点开始派出一些tank去占领一些电站，坦克到每个电站都有一定距离，而占领每个电站之后可以得到一定电量，距离就相当于体积v，电量就相当于价值w，这不是就01背包吗？01背包通常的问法是给定体积，求获得最大的价值，这里的问法是给定价值，求恰好得到或多于该价值时的最小体积。我们只要从前向后搜索，找到第一个大于该价值的体积即可。
不过一开始我就被坑了，我令inf=0x7fffffff,然后就wa了好多次，最后该成小一些的数，就过了，orz；
View Code
1 #include<iostream> 2 #include<cstring> 3 const int N=111; 4 const int inf=0x7fffff; 5 using namespace std; 6 int n,m; 7 int edge[N][N]; 8 int visited[N]; 9 int dist[N]; 10 int dp[N*N],power[N]; 11 12 void Dijkstra(int v0){ 13 memset(visited,0,sizeof(visited)); 14 for(int i=1;i<=n;i++){ 15 dist[i]=edge[v0][i]; 16 } 17 visited[v0]=1; 18 for(int i=1;i<n;i++){ 19 int min=inf,u=v0; 20 for(int j=1;j<=n;j++){ 21 if(!visited[j]&&dist[j]<min){ 22 min=dist[j],u=j; 23 } 24 } 25 if(min==inf)return ; 26 visited[u]=1; 27 for(int k=1;k<=n;k++){ 28 if(!visited[k]&&dist[u]+edge[u][k]<dist[k]){ 29 dist[k]=dist[u]+edge[u][k]; 30 } 31 } 32 } 33 } 34 35 int main(){ 36 int _case; 37 scanf("%d",&_case); 38 while(_case--){ 39 scanf("%d%d",&n,&m); 40 for(int i=0;i<=n;i++){ 41 for(int j=0;j<=n;j++){ 42 if(i==j){ 43 edge[i][j]=0; 44 }else 45 edge[i][j]=inf; 46 } 47 } 48 int x,y,d; 49 for(int i=1;i<=m;i++){ 50 scanf("%d%d%d",&x,&y,&d); 51 if(d<edge[x][y]){ 52 edge[x][y]=edge[y][x]=d; 53 } 54 } 55 for(int i=1;i<=n;i++){ 56 scanf("%d",&power[i]); 57 } 58 Dijkstra(0); 59 bool flag=true; 60 int v=0,w=0; 61 for(int i=1;i<=n;i++){ 62 w+=power[i]; 63 v+=dist[i]; 64 if(dist[i]==inf){ 65 flag=false; 66 break; 67 } 68 } 69 if(!flag){ 70 printf("impossible\n"); 71 continue; 72 } 73 for(int i=0;i<=v;i++){ 74 dp[i]=0; 75 } 76 for(int i=1;i<=n;i++){ 77 for(int j=v;j-dist[i]>=0;j--){ 78 dp[j]=(dp[j-dist[i]]+power[i])>dp[j]?(dp[j-dist[i]]+power[i]):dp[j]; 79 } 80 } 81 w=w/2+1; 82 for(int i=1;i<=v;i++){ 83 if(dp[i]>=w){ 84 printf("%d\n",i); 85 break; 86 } 87 } 88 } 89 return 0; 90 }