题目大意就是 你有足够多的坦克，让你用尽量多的坦克去占领电厂。有N+1各节点，0~n ，0为出发点，1~n为电厂。要想控制摧毁电厂，战胜对方，只需要占领一般的电量即可。但是特克会耗油，所一给你m条路，让你去计算最小耗电量~而且如果坦克不能通过m条路到达任意一个电厂的话就输出'impossible'
连接：
代码：dij
View Code 1 #include2 #include 3 #define maxn 0x5fffffff 4 int map[105][105]; 5 int dis[105]; 6 void inint(int n) 7 { 8 int j,i; 9 for(i = 0;i <= n;i++)10 {11 for(j = 0;j <= n;j++)12 if(i != j)map[i][j] = maxn;13 else map[i][j] = 0;14 }15 }16 void disj(int n)17 {18 int vis[105] = { 0};19 int pre,i,j,k,min;20 pre = 0;21 for(i = 0;i <= n;i++)22 dis[i] = map[pre][i];23 vis[pre] = 1;24 25 for(k = 1;k <= n;k++)26 {27 for(i = 0;i <= n;i++)28 {29 if(!vis[i] && dis[i] > dis[pre]+map[pre][i])30 dis[i] = dis[pre]+map[pre][i];31 }32 min = maxn;33 for(i = 0;i <= n;i++)34 if(min > dis[i] && !vis[i])35 min = dis[i],pre = i;36 37 vis[pre] = 1;38 }39 }40 int main()41 {42 int T,n,m,i,j,a,b,c,sum,pow[105],spow,f[20005];43 scanf("%d",&T);44 while(T--)45 {46 scanf("%d %d",&n,&m);47 inint(n);48 for(i = 0;i < m;i++)49 {50 scanf("%d%d%d",&a,&b,&c);51 if(c < map[a][b])52 map[a][b] = map[b][a] = c;53 }54 55 disj(n);56 spow = sum = 0;57 for(i = 1;i <= n;i++)58 scanf("%d",pow+i),spow+=pow[i];59 int leap = 0;60 for(i = 1;i <= n;i++)61 {62 if(dis[i] != maxn)63 sum += dis[i];64 else65 leap = 1;66 }67 if(leap)68 puts("impossible");69 else70 {71 memset(f,0,sizeof(f));72 for(i = 1;i <= n;i++)73 {74 for(j = sum;j >= dis[i];j--)75 {76 if(f[j] < f[j-dis[i]]+pow[i])77 f[j] = f[j-dis[i]]+pow[i];78 }79 }80 for(i = 0;i <= sum;i++)81 if(f[i] > spow/2)82 {83 printf("%d\n",i);84 break;85 }86 }87 }88 return 0;89 }
floyd
View Code 1 #include2 #include 3 #define maxn 10000050 4 int map[105][105]; 5 int dis[105]; 6 void inint(int n) 7 { 8 int j,i; 9 for(i = 0;i <= n;i++)10 {11 for(j = 0;j <= n;j++)12 if(i != j)map[i][j] = maxn;13 else map[i][j] = 0;14 }15 }16 17 int main()18 {19 int T,n,m,i,j,k,a,b,c,sum,pow[105],spow,f[100005];20 scanf("%d",&T);21 while(T--)22 {23 scanf("%d %d",&n,&m);24 inint(n);25 for(i = 0;i < m;i++)26 {27 scanf("%d%d%d",&a,&b,&c);28 if(c < map[a][b])29 map[a][b] = map[b][a] = c;30 }31 32 spow = sum = 0;33 for(i = 1;i <= n;i++)34 scanf("%d",pow+i),spow+=pow[i];35 36 for(k = 0;k <= n;k++)37 {38 for(i = 0;i <= n;i++)39 {40 for(j = 0;j <= n;j++)41 if(map[i][j] > map[i][k]+map[k][j])42 map[i][j] = map[i][k]+map[k][j];43 }44 }45 46 for(i = 1;i <= n;i++)47 {48 dis[i] = map[0][i];49 if(dis[i] != maxn)50 sum += dis[i];51 }52 53 memset(f,0,sizeof(f));54 for(i = 1;i <= n;i++)55 {56 for(j = sum;j >= dis[i];j--)57 if(f[j] < f[j-dis[i]] + pow[i])58 f[j] = f[j-dis[i]] + pow[i];59 }60 61 for(i = 0;i <= sum;i++)62 {63 if(f[i] >= spow/2+1)64 {65 printf("%d\n",i);66 break;67 }68 }69 if(i > sum)70 puts("impossible");71 }72 return 0;73 }
