p2377.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1001;
const int MAXM = 20001;
int parent[MAXN],rank[MAXN],cnt[MAXN];
struct road{ int a,b,c; };
road f[MAXM];
bool vi[MAXN];
bool cmp(road a,road b){ return a.c > b.c; }
void MakeSet(int x){
    parent[x] = x;
    rank[x] = 0;
    cnt[x] = 1;
}
int FindSet(int x){
    if(x == -1 || x >= MAXN) return -1;
    else 
        if(parent[x] != -1 && parent[x] != x)
            parent[x] = FindSet(parent[x]);
    return parent[x];
}
int UnionSet(int x,int y){
    x = FindSet(x);
    y = FindSet(y);
    if(x == y) return -1;
    if(x == -1) return y;
    if(y == -1) return x;
    if(rank[x] > rank[y]){
        parent[y] = x;
        cnt[x] += cnt[y];
        return x;
    }
    else{
        parent[y] = x;
        cnt[y] += cnt[x];
        if(rank[x] == rank[y])
            ++rank[y];
        return y;
    }
}
int main(){
  int n,m;
    cin >> n >> m;
    memset(vi,0,sizeof(vi));
    for(int i = 0;i < m;++i) scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
    sort(f,f+m,cmp);
    int ans(0),link(0);
    for(int i = 0;i <= n;++i) MakeSet(i);
    for(int j = 0;link < n-1 && j < m;++j)
        if(FindSet(f[j].a) != FindSet(f[j].b)){
            if(!vi[f[j].a])
                vi[f[j].a] = 1;
            if(!vi[f[j].b])
                vi[f[j].b] = 1;
            ++link;
            UnionSet(f[j].a,f[j].b);
            ans += f[j].c;
        }
    if(link < n-1) puts("-1");
    else cout << ans << endl;
}