POJ 2395 Out of Hay(最小生成树中的最大长度）

POJ 2395 Out of Hay

　　本题是要求最小生成树中的最大长度， 无向边，初始化es结构体时要加倍，别忘了init（n）并查集的初始化，同时要单独标记使用过的边数，

判断ans==n-1时，即找到了最大边。

　　

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int par[2005];
int ran[2005];
struct edge{
    int from,to,cost;
};
edge es[20005];
bool cmp(const edge& x,const edge& y){
    return x.cost<y.cost;
}
void init(int n){
    for(int i=0;i<n;i++){
         par[i]=i;
         ran[i]=0;
    }
}
int find(int x){
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(ran[x]<ran[y]) par[x]=y;
    else{
        par[y]=x;
        if(ran[x]==ran[y])
            ran[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}
int main()
{    
    int n,m,k,res;
    scanf("%d%d",&n,&m);
    int a,b,c;
    k=0;
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        a--;b--;
        es[k].from=a;
        es[k].to=b;
        es[k++].cost=c;
        es[k].from=b;
        es[k].to=a;
        es[k++].cost=c;
    }
    sort(es,es+k,cmp);
    init(n);//注意并查集的初始化
    int ans=0;
    for(int i=0;i<k;i++){
        edge e=es[i];
        if(!same(e.to,e.from)){
            unite(e.to,e.from);
            ans++;//单独标记已用过的边数
            if(ans==n-1){
                res=e.cost;
                break;
            }
        }
    }
    printf("%d
",res);
    return 0;
}