nyoj 925 国王的烦恼（最小生成树）

/*

    题意：N个城市中每两个城市有多条路径连接，可是因为路径存在的天数是有限的！以为某条路经不存在了

    导致N个城市不能连通了，那么村名们就会抗议！问一共会有多少次抗议！

    思路：最小生成树....我们用最大边来建立树！只要有最大边将节点连接并保证连通！那么边权小的值

    就可以忽略了！最后将生成树中由（最大边组成的）去重（相同的值只有一次抗议）！这时剩下边的数值就是

    答案了！ 

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#define M 10005

#define N 100005

using namespace std;

struct EDGE{

   int u, v, tt;       

};

int f[N];

int n, m;

int getFather(int x){

   return x==f[x] ? x:f[x]=getFather(f[x]);    

}

bool Union(int a, int b){

    int fa=getFather(a), fb=getFather(b);

    if(fa!=fb){

       f[fa]=fb;

       return true;

    }     

    return false;

bool cmp(EDGE a, EDGE b){

   return a.tt > b.tt;

EDGE edge[N];

int xx[N];

int main(){

   while(scanf("%d%d", &n, &m)!=EOF){

        for(int i=1; i<=n; ++i)

           f[i]=i;

        for(int i=0; i<m; ++i)

           scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].tt);                                

        sort(edge, edge+m, cmp);//将边权按照从大到小排序！ 

        int cnt=0;

           if(Union(edge[i].u, edge[i].v)) 

              xx[cnt++]=edge[i].tt;

        cnt=unique(xx, xx+cnt)-xx;//去重 

        printf("%d\n", cnt);

   }

   return 0;    

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3906569.html，如需转载请自行联系原作者