【kruscal】【最小生成树】【并查集扩展】bzoj3714 [PA2014]Kuglarz

ORZ：http://www.cnblogs.com/zrts/p/bzoj3714.html
 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define N 2010
 5 int fa[N],rank[N],n,m,tot;
 6 long long ans;
 7 struct Edge{int u,v,w;}edges[(N*N)>>1];
 8 bool operator < (const Edge &a,const Edge &b){return a.w<b.w;}
 9 void init(){for(int i=1;i<=n;i++)fa[i]=i;}
10 int Res;char C;
11 inline int R()
12 {
13     Res=0;C='*';
14     while(C<'0'||C>'9')C=getchar();
15     while(C>='0'&&C<='9'){Res=Res*10+(C-'0');C=getchar();}
16     return Res;
17 }
18 int findroot(int x)
19 {
20     if(x==fa[x]) return x;
21     int rt=findroot(fa[x]);
22     fa[x]=rt;
23     return rt;
24 }
25 inline void Union(const int &U,const int &V)
26 {
27     if(rank[U]<rank[V]) fa[U]=V;
28     else
29       {
30           fa[V]=U;
31           if(rank[U]==rank[V]) rank[U]++;
32       }
33 }
34 int main()
35 {
36     n=R(); init();
37     for(int i=1;i<=n;i++)
38       for(int j=i;j<=n;j++)
39         edges[++m]=(Edge){i-1,j,R()};
40     sort(edges+1,edges+m+1);
41     for(int i=1;i<=m;i++)
42       {
43           int f1=findroot(edges[i].u),f2=findroot(edges[i].v);
44           if(f1!=f2)
45             {
46                 Union(f1,f2);
47                 ans+=(long long)edges[i].w;
48                 tot++;
49                 if(tot==n) break;
50             }
51       }
52     printf("%lld
",ans);
53     return 0;
54 }