题目1028:继续畅通工程 九度OJ

xiaoxiao2021-02-27  268

题目1028:继续畅通工程

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:5028

解决:2097

题目描述:     省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。 输入:     测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。     当N为0时输入结束。 输出:     每个测试用例的输出占一行,输出全省畅通需要的最低成本。 样例输入: 3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0 样例输出: 3 1 0 来源: 2008年浙江大学计算机及软件工程研究生机试真题 #include <cstdio> #include <algorithm> #define MAX 105 using namespace std; int tree[MAX]; int findRoot(int x){ if(tree[x]==-1)return x; else{ int temp=findRoot(tree[x]); tree[x]=temp; return temp; } } struct edge{ int node1,node2,length; bool operator<(const struct edge &b)const{ return length<b.length; } }edge[6000]; int main(){ int n; while(scanf("%d",&n)!=EOF&&n!=0){ for(int i=0;i<MAX;i++){ tree[i]=-1; } int p1,p2,l,tag; int size=0; int forlimit=n*(n-1)/2; for(int i=0;i<forlimit;i++){ scanf("%d%d%d%d",&p1,&p2,&l,&tag); if(tag==0){ edge[size].node1=p1; edge[size].node2=p2; edge[size].length=l; size++; }else{ p1=findRoot(p1); p2=findRoot(p2); if(p1!=p2){ tree[p1]=p2; } } } sort(edge,edge+size); int ans=0; int a,b; for(int i=0;i<size;i++){ a=findRoot(edge[i].node1); b=findRoot(edge[i].node2); if(a!=b){ ans+=edge[i].length; tree[a]=b; } } printf("%d\n",ans); } return 0; } 跟上一道题,比起来就是多了已建成和未建成的标记。 已建成的显然开销为0. 先根据已建成的道路得到集合,在从未建成的道路中找开销最小的道路。
转载请注明原文地址: https://www.6miu.com/read-4680.html

最新回复(0)