pta7-20 畅通工程之局部最小花费问题（Kruskal算法）

题目链接：https://pintia.cn/problem-sets/15/problems/897

题意：给出n个城镇，然后给出n×（n-1）/2条边，即每两个城镇之间的边，包含起始点，终点，修建的花费，以及是否已经修建。需要求出最小花费让城镇两两可达。

思路：最小生成树变形题，首先将边排序，将已经修好的放在前面，未修好的放在后面，并均按照花费升序排列。之后用并查集将已经连通的城镇并在一起，然后对未修好的道路使用kruskal算法，直到所有的城镇两两可达，此时的花费即最小。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct node{
 5     int s,e,c,f;
 6 }a[10000];
 7 
 8 bool cmp(node x,node y){
 9     if(x.f==y.f) return x.c<y.c;
10     return x.f>y.f;
11 }
12 
13 int n,m,res;
14 int root[105];
15 
16 int getr(int k){
17     if(root[k]==k) return k;
18     else return root[k]=getr(root[k]);
19 }
20 
21 int main(){
22     scanf("%d",&n);
23     m=n*(n-1)/2;
24     for(int i=0;i<m;++i)
25         scanf("%d%d%d%d",&a[i].s,&a[i].e,&a[i].c,&a[i].f);
26     sort(a,a+m,cmp);
27     for(int i=1;i<=n;++i)
28         root[i]=i;
29     for(int i=0;i<m;++i){
30         int rs=getr(a[i].s),re=getr(a[i].e);
31         if(a[i].f==1)
32             root[re]=rs;
33         else if(rs!=re)
34             res+=a[i].c,root[re]=rs;    
35     }
36     printf("%d
",res);
37 }