HDU1879"继续畅通工程"

柔情只为你懂 2022-05-19 12:58 162阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> Problem Description 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。 &nbsp; Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1&lt; N &lt; 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。 当N为0时输入结束。 &nbsp; Output 每个测试用例的输出占一行，输出全省畅通需要的最低成本。 &nbsp; Sample Input 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 &nbsp; Sample Output 3 1 0 </td> 
 </tr> 
 </tbody> 
</table>

#include<stdio.h>
 #define MAX 102
 #define MAXCOST 100000
 int graph[102][102];
 int x,y,cost,z;
 int n;
 
 void prim(){
 	int low[MAX];
 	int set[MAX];
 	for(int i=1;i<=n;i++)
 	{
 		low[i]=graph[1][i];
 		set[i]=0;
 	}
 	set[1]=1;
 	int k=1,sum=0;
 	for(int i=2;i<=n;i++)
 	{
 		int min=MAXCOST;
 		for(int j=2;j<=n;j++)
 			if(!set[j]&&low[j]<min)
 			{
 				k=j;
 				min=low[j];
 			}
 		
 		set[k]=1;
 		sum+=min;
 		for(int j=2;j<=n;j++)
 		{
 			if(!set[j]&&low[j]>graph[k][j])
 			low[j]=graph[k][j];
 		}
 	}
 	printf("%d\n",sum);
 }
 
 int main()
 {
 	int m,i,j;
 	while(~scanf("%d",&n)&&n)
 	{
 		m=n*(n-1)/2;
 		for(i=1;i<=n;i++)
 			for(j=1;j<=n;j++)
 				graph[i][j]=MAXCOST;
 		for(i=0;i<m;i++)
 		{
 			scanf("%d%d%d%d",&x,&y,&cost,&z);
 			if(z==0)
 			{
 				if(graph[x][y]>cost)
 				graph[x][y]=graph[y][x]=cost;
 			}
 			else
 				graph[x][y]=graph[y][x]=0;
 		}
 		prim();
 	}
 	return 0;
 }