填坑...P1546 最短网络 Agri-Net

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

28

 1 #include 2 #include
 3 using namespace std;
 4 #define maxn 10005
 5 struct UnionFindSet
 6 {
 7     int x,y,v;
 8     int fat[maxn];
 9     UnionFindSet()
10     {
11         for(int i=0;i)
12             fat[i]=i;
13         x=y=v=0;
14     }
15     inline int father(int x)
16     {
17         if(fat[x]!=x)
18             fat[x]=father(fat[x]);
19         return fat[x];
20     }
21     inline void unionn(int x,int y)
22     {
23         int fa=father(x);
24         int fb=father(y);
25         if(fa!=fb)
26             fat[fa]=fb;
27     }
28 };
29 struct Edge
30 {
31     int pre,to,w;
32     bool operator const Edge &b) const
33     {
34         return this->w  b.w;
35     }
36 };
37 Edge edge[maxn];
38 int cnt;
39 inline void AddEdge(int u,int v,int w)
40 {
41     edge[++cnt].pre=u;
42     edge[cnt].to=v;
43     edge[cnt].w=w;
44 }
45 UnionFindSet s;
46 int Kruskal(int EdgeNumber)
47 {
48     sort(edge+1,edge+1+EdgeNumber);
49     int n=1,ans=0;
50     while(n1)
51     {
52         if(s.father(edge[n].pre)!=s.father(edge[n].to))
53         {
54             s.unionn(edge[n].pre,edge[n].to);
55             ans+=edge[n].w;
56         }
57         n++;
58     }
59     return ans;
60 }
61 int main()
62 {
63     int n,t;
64     scanf("%d",&n);
65     for(int i=1;i)
66         for(int j=1;j)
67         {
68             scanf("%d",&t);
69             if(t)
70                 AddEdge(i,j,t);
71         }
72     printf("%d\n",Kruskal(n*n-n));
73     return 0;
74 }