HDU 1863 – 畅通工程 [并查集+Kruskal算法]

vjudge链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23261

题意:给定m个村庄和n个有可能建设的道路的成本,要想连起所有村庄,求最小道路成本,或者输出不能连起所有村庄。

转化为最小生成树+并查集问题,如果边数<m-1则不能连接所有村庄。

 


#include "cstdio"
#include "algorithm"
using namespace std;

const int maxn = 105;
int n, m, par[maxn];
struct edge{
    int u, v, cost;
    bool operator < (const edge & rhs) const {return cost < rhs.cost;}
}e[maxn];

int Find(int x){ return x==par[x] ? x : par[x] = Find(par[x]);}
void Unite(int x, int y){x = Find(x), y = Find(y), par[x] = y;}
bool Same(int x, int y) {return Find(x) == Find(y);}
void init(int n){for(int i = 0; i <= n; ++i) par[i] = i;}


int main(){
    while(~scanf("%d%d", &n, &m) && n){
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].cost);
        init(n);
        sort(e, e + n);
        int cnt = 0, ans = 0;
        for(int i = 0; i < n; ++i){
            edge & cur = e[i];
            if(!Same(cur.u, cur.v)){
                Unite(cur.u, cur.v);
                ans += cur.cost;
                ++cnt;
            }
        }
        if(cnt < m - 1) puts("?");
        else printf("%d\n", ans);
    }
    return 0;
}

欢迎留言