HDU 3339 In Action 最短路+01背包~

题目大意就是 你有足够多的坦克，让你用尽量多的坦克去占领电厂。有N+1各节点，0~n ，0为出发点，1~n为电厂。要想控制摧毁电厂，战胜对方，只需要占领一般的电量即可。但是特克会耗油，所一给你m条路，让你去计算最小耗电量~而且如果坦克不能通过m条路到达任意一个电厂的话就输出'impossible'

连接：http://acm.hdu.edu.cn/showproblem.php?pid=3339

代码：dij

View Code

1 #include <stdio.h>
 2 #include <string.h>
 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             else
65             leap = 1;
66         }
67         if(leap)
68         puts("impossible");
69         else
70         {
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 #include <stdio.h>
 2 #include <string.h>
 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 }      

转载于:https://www.cnblogs.com/0803yijia/archive/2012/08/15/2639678.html