nyoj 925 國王的煩惱（最小生成樹）

 1 /*
 2     題意：N個城市中每兩個城市有多條路徑連接，可是因為路徑存在的天數是有限的！以為某條路經不存在了
 3     導致N個城市不能連通了，那么村名們就會抗議！問一共會有多少次抗議！
 4     
 5     思路：最小生成樹....我們用最大邊來建立樹！只要有最大邊將節點連接并保證連通！那么邊權小的值
 6     就可以忽略了！最后將生成樹中由（最大邊組成的）去重（相同的值只有一次抗議）！這時剩下邊的數值就是
 7     答案了！ 
 8 */
 9 #include<iostream>
10 #include<cstring>
11 #include<cstdio>
12 #include<algorithm>
13 #include<vector>
14 #define M 10005
15 #define N 100005
16 using namespace std;
17 struct EDGE{
18    int u, v, tt;       
19 };
20 
21 int f[N];
22 int n, m;
23 int getFather(int x){
24    return x==f[x] ? x:f[x]=getFather(f[x]);    
25 }
26 
27 bool Union(int a, int b){
28     int fa=getFather(a), fb=getFather(b);
29     if(fa!=fb){
30        f[fa]=fb;
31        return true;
32     }     
33     return false;
34 }
35 
36 bool cmp(EDGE a, EDGE b){
37    return a.tt > b.tt;
38 }
39 
40 EDGE edge[N];
41 int xx[N];
42 int main(){
43    while(scanf("%d%d", &n, &m)!=EOF){
44         for(int i=1; i<=n; ++i)
45            f[i]=i;
46         for(int i=0; i<m; ++i)
47            scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].tt);                                
48         sort(edge, edge+m, cmp);//將邊權按照從大到小排序！ 
49         int cnt=0;
50         for(int i=0; i<m; ++i)
51            if(Union(edge[i].u, edge[i].v)) 
52               xx[cnt++]=edge[i].tt;
53         cnt=unique(xx, xx+cnt)-xx;//去重 
54         printf("%d\n", cnt);
55    }
56    return 0;    
57 }
58

轉載于:https://www.cnblogs.com/hujunzheng/p/3906569.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531763.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531763.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531763.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！