克鲁斯卡尔Kruskal

Description

在B 国里，有N 个城市，每个城市有一个发达程度a[i]。B 要修建一些道路，修建这条道路的花费为cost[i]，把这些城市连起来，使得任意2 个城市之间，有且只有1 条路相联通。最后这些道路建成时，每个城市对B 国的经济会做出贡献，贡献度为a[i] *(i 这个城市它所直接相连的城市数)（但由于B 国的人民只热衷于翻墙，所以经济并不发达，这个贡献值会远远小于cost）。这样B 就得出了一个对这个方案的代价，为总cost-总贡献值，现在B 要求一种方案使得这个代价最小。

Input

第一行两个数n，m，表示城市数量，可以修建的道路条数m。
接下来1 行n 个数，表示a[i]。
接下来M 行，每行3 个数，x,y,z，表示一条从x 到y 的双向边，修这条路
的代价为z。

Output

一个数表示最小代价。

Sample Input

Sample Output

34

思路:把代价看作 每条边-这条边连接城市的价值,这样就可以跑最小生成树了~

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxx 100010
 5 #define ll long long
 6 using namespace std;
 7 struct Edge{
 8     int u,v,w;
 9 }e[maxx];
10 int a[maxx];
11 int father[maxx];
12 int n,m,x,y,v,cnt,blockcnt;
13 ll ans;
14 bool cmp(Edge a,Edge b){
15     return a.w<b.w;
16 }
17 int find(int x){//找x所对应的根结点标号
18     int s;
19     for(s=x;father[s]>=0;s=father[s]){//find father
20         while(s!=x){//路径压缩
21             int tmp=father[x];
22             father[x]=s;
23             x=tmp;
24         }
25     }
26     return s;
27 }
28 void connect(int u,int v){
29     int r1=find(u),r2=find(v);
30     int tmp=father[r1]+father[r2];//集合元素个数
31     if(father[r1]>father[r2]){//r2元素多,r1接到r2上(优化)
32         father[r1]=r2;
33         father[r2]=tmp;//更新集合个数
34     }
35     else{
36         father[r2]=r1;
37         father[r1]=tmp;
38     }
39     return ;
40 }
41 int main(){
42     scanf("%d%d",&n,&m);
43     blockcnt=n;
44     for(int i=1;i<=n;i++){
45         scanf("%d",&a[i]);
46     }
47     for(int i=1;i<=m;i++){
48         scanf("%d%d%d",&x,&y,&v);
49         e[i].u=x;
50         e[i].v=y;
51         e[i].w=v-a[x]-a[y];
52     }
53     sort(e+1,e+1+m,cmp);
54     for(int i=1;i<=n;i++){
55         father[i]=-1;
56     }
57     for(int i=1;i<=m;i++){
58         if(blockcnt==1)
59             break;
60         if(find(e[i].u)!=find(e[i].v)){
61             connect(e[i].u,e[i].v);
62             blockcnt--;
63             ans+=e[i].w;
64         }
65     }
66     printf("%lld
",ans);
67     return 0;
68 }