sdut 2421 PowerOutage（最小生成树）

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2421

利用最小生成树求出总权值×2 - 最大的叶子节点所经路径的权值

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define inf 0x3f3f3f
 5 using namespace std;
 6 int b[110][110];
 7 void  prim(int n)
 8 {
 9     int i,j,pos,min;
10     int d[110];
11     int vis[110];
12     int max[110],h=0;
13     memset(vis,0,sizeof(vis));
14     memset(max,0,sizeof(max));
15     for(i=1;i<=n;i++)
16     {
17         d[i]=b[0][i];
18         if(d[i]<inf)
19         {
20             max[i]=d[i];
21             if(h<max[i])
22             h=max[i];
23         }
24 
25     }
26     vis[0]=1;
27     long long int ans=0;
28     for(i=0;i<=n;i++)
29     {
30         min=inf;
31         for(j=1;j<=n;j++)
32         {
33             if(!vis[j]&&d[j]<min)
34             {
35                 pos=j;
36                 min=d[j];
37             }
38         }
39         if(min==inf)
40         break;
41         vis[pos]=1;
42         ans+=min;
43         for(j=1;j<=n;j++)
44         {
45             if(!vis[j]&&b[pos][j]<d[j])
46             {
47                 d[j]=b[pos][j];
48                 max[j]=max[pos]+d[j];//更新j点到零的最大长度
49                 if(h<max[j])
50                 h=max[j];
51             }
52 
53         }
54     }
55     printf("%lld\n",ans*2-h);
56 }
57 int main()
58 {
59     int n,i,x,y,d,max;
60     while(~scanf("%d",&n))
61     {
62         memset(b,inf,sizeof(b));
63         max=0;
64         for(i=0;i<n;i++)
65         {
66             scanf("%d%d%d",&x,&y,&d);
67             if(d<b[x][y])
68             {
69                 b[x][y]=d;
70             }
71             b[y][x]=b[x][y];
72             if(max<x)
73             max=x;
74             if(max<y)
75             max=y;
76         }
77         prim(max);
78     }
79     return 0;
80 }