公路村村通
分数 30
全屏浏览
切换布局
作者 陈越
单位 浙江大学
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数 n（≤1000）和候选道路数目 m（≤3n）；随后的 m 行对应 m 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 n 编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12
1.分析
结构体数组存图，按照权重从小到大排序，kruskal算法计算。
2.代码
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=1e4+10;
struct node{int from,to,w;
}edge[MAX]; //结构体
int N,M,re,c;
bool cmp(node a,node b){ //排序函数return a.w<b.w;
}
int findRoot(int fa[],int v){ //找生成树的结点int t=v;while(fa[t]>-1){t=fa[t];}return t;
}
void Kruskal(){int v1,v2;int fa[MAX];for(int i=1;i<=N;i++) fa[i]=-1; //初始化for(int num=1,i=0;num<=N&&i<M;i++){v1=findRoot(fa,edge[i].from);v2=findRoot(fa,edge[i].to);if(v1!=v2){ fa[v2]=v1;re+=edge[i].w;num++;c=num; //记录结点个数}}
}
int main(){cin>>N>>M; for(int i=0;i<M;i++){ //输入cin>>edge[i].from>>edge[i].to>>edge[i].w;}sort(edge,edge+M,cmp);Kruskal();if(c==N){cout<<re<<endl;} //输出else cout<<"-1"<<endl;return 0;
}
