百度之星资格赛, 1002---度度熊的王国战略

本来好像是一道什么割边的, 还要用什么优化来着;

但是显然不会啊, 直接瞎搞了一个, 先用并查集判连通块个数, 如果多个连通块那代价就是0了, 只有一个的情况下再去掉代价最小的点的代价就是答案了;

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 100005;
int w[maxn], p[maxn];

void init(int n){
    for(int i=0;i<=n;i++){
        p[i] = i;
    }
}

int find(int x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}

void cmb(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    p[x] = y;
}

bool same(int x, int y){
    return find(x) == find(y);
}

int main(){
    int n, m, u, v, p;
    while(scanf("%d%d", &n, &m) == 2){
        memset(w, 0, sizeof(w));
        for(int i=0;i<m;i++){
            scanf("%d%d%d", &u, &v, &p);
            if(u == v) continue;
            cmb(u, v);
            w[u] += p;
            w[v] += p;
        }
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(find(i) == i) cnt++;
        }
        if(cnt > 1){
            printf("0\n");
            continue;
        }
        sort(w + 1, w + n + 1);
        printf("%d\n", w[1]);
    }
    return 0;
}