首页 > 代码库 > hdoj 1863 畅通工程 【最小生成树】+【kruskal】
hdoj 1863 畅通工程 【最小生成树】+【kruskal】
题意:。。。
难点:如何判断是不是信息不全:在输入的时候建立并查集,之后判断有几个节点就可以了,剩下的就是kruskal算法。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #define MAXN 105 #define INF 0x3f3f3f3f using std::sort; struct node{ int from; int to; int w; }edges[MAXN*MAXN]; int fat[MAXN], n, m; int f(int x){ if(fat[x] != x) fat[x] = f(fat[x]); return fat[x]; } int cmp(node a, node b) { return a.w < b.w; } int kruskal() { int i, ans = 0; for(i = 1; i<= m; i ++){ //这里也要初始化,因为前面的被修改过了 fat[i] = i; } sort(edges, edges+n, cmp); for(i = 0; i < n; i ++){ int x = f(edges[i].from); int y = f(edges[i].to); if(x!=y){ fat[x] = y; ans += edges[i].w; } } return ans; } int main() { int a, b, c, i; while(scanf("%d%d", &n, &m), n){ for(i = 1; i <= m; i ++){ //初始化 fat[i] = i; } for(i = 0;i < n; i ++){ scanf("%d%d%d", &a, &b, &c); edges[i].from = a; edges[i].to = b; edges[i].w = c; int x = f(a); //建立并查集 int y = f(b); if(x!=y){ fat[x] = y; } } int flag = 0, cou = 0; for(i = 1; i <= m; i ++){//判断是不是有多个节点,如果有多个节点那么肯定是有村庄是孤立的 if(fat[i] == i){ cou ++; if(cou > 1){ flag = 1; break; } } } if(flag){ printf("?\n"); continue; } int ans = kruskal(); printf("%d\n", ans); } return 0; }题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1863
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。