Kruskal || BZOJ 1601: [Usaco2008 Oct]灌水 || Luogu P1550 [USACO08OCT]打井Watering Hole

题解：无
代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define ll long long
 6 using namespace std;
 7 const int maxn=350;
 8 int N,W[maxn],fa[maxn],num_edge=0,edge_head[maxn];
 9 ll Z,ans;
10 struct Edge{int from,to,nx;ll dis;}edge[2*maxn*maxn];
11 inline void Add_edge(int from,int to,ll dis){
12     edge[++num_edge].nx=edge_head[from];
13     edge[num_edge].from=from;
14     edge[num_edge].to=to;
15     edge[num_edge].dis=dis;
16     edge_head[from]=num_edge;
17     return;
18 }
19 inline int getf(int n){
20     if(fa[n]==n)return n;
21     fa[n]=getf(fa[n]);
22     return fa[n];
23 }
24 inline bool cmp(const Edge&a,const Edge&b){return a.dis<b.dis;}
25 void Kruskal(){
26     int cnt=0;
27     for(int i=0;i<=N;i++)fa[i]=i;
28     sort(edge+1,edge+num_edge+1,cmp);
29     for(int i=1;i<=num_edge;i++){
30         int x=edge[i].from,y=edge[i].to;
31         int fx=getf(x),fy=getf(y);
32         if(fa[x]!=fa[y]){
33             cnt++;
34             fa[fx]=fy;
35             ans+=edge[i].dis;
36         }
37     }
38     return;
39 }
40 int main(){
41     scanf("%d",&N);
42     for(int i=1;i<=N;i++)scanf("%d",&W[i]);
43     for(int i=1;i<=N;i++)Add_edge(0,i,W[i]);
44     for(int i=1;i<=N;i++)
45         for(int j=1;j<=N;j++){
46             scanf("%lld",&Z);
47             Add_edge(i,j,Z);
48         }
49     Kruskal();
50     printf("%lld
",ans);
51     return 0;
52 }
By:AlenaNuna