首页 > 代码库 > POJ 1287 Networking
POJ 1287 Networking
题目链接：
poj.org/problem?id=1287
题目大意：
你被分派到去设计一个区域的连接点，给出你每个点对之间的路线，你需要算出连接所有点路线的总长度。
题目输入：
一个数字n 代表有 n个顶点， 一个数字 m 有m条边。
接下来m行是 m条边的信息， 起点 终点 权值
题目输出 ：
输出最小生成树的值
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 22220struct Edge{ int s, e, w; Edge(int s=0,int e=0,int w=0):s(s), e(e), w(w) {} bool friend operator < (Edge A, Edge B) { return A.w < B.w; }}P[maxn];int n, m;int Par[maxn];void Init();int Kruskal();int GetPar(int a);void Meger(int a,int b);int main(){ int s, e, w; while(cin >> n, n) { cin >> m; Init(); for(int i=0; i<m; i++) { cin >> s >> e >>w; P[i] = Edge(s,e,w); } sort(P, P+m); int ans = Kruskal(); cout << ans << endl; } return 0;}void Init(){ for(int i=0; i<=n; i++) { Par[i]=i; }}int Kruskal(){ int sum = 0; int Nnode = 1; for(int i=0; i<m; i++) { if( GetPar(P[i].s) != GetPar(P[i].e) ) { sum += P[i].w; Meger(P[i].s,P[i].e); Nnode ++; } if(Nnode == n) return sum; } return 0;}int GetPar(int a){ if(Par[a] != a) Par[a] = GetPar(Par[a]); return Par[a];}void Meger(int a,int b){ Par[GetPar(a)] = Par[GetPar(b)];}
POJ 1287 Networking
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。