Open project

Problem Description

The goal of the provincial government’s “Unimpeded Project” is to make road access available to any two villages in the province (but not necessarily by direct road, as long as it is indirectly accessible by road). After the survey and evaluation, the resulting statistical tables show the costs of a number of possible roads. Please write a program to calculate the lowest cost required for the province to be unblocked.

Input

The test input contains several test cases. Line 1 of each test case gives the number of roads (N) and villages (M) evaluated (< 100); The following N lines correspond to the cost of the road between the villages. Each line gives a pair of positive integers, the number of the two villages, and the cost of the road between the two villages (also a positive integer). Villages are numbered from 1 to M for simplicity. When N is 0, all input ends and the corresponding result is not output.

Output

For each test case, output the lowest cost required for province-wide flow in line 1. If statistical data is insufficient to ensure smooth operation, output “? “. .

Sample Input

1 3 2 2 3 4 1 3 2 3 2 0 100

Sample Output

3?

Description:

Lowest cost to make m villages unblocked, if not unblocked output?

Program code:

#include<stdio.h>
#include<algorithm>
using namespace std;
struct data{
	int u,v,w;
}e[110];
int f[110],n,m;
int cmp(struct data x,struct data y);
int getf(int u);
int merge(int u,int v);
int main(a)
{
	int i,j,k,sum,count;
	while(scanf("%d%d",&n,&m)! =EOF) {if(n==0)
			break;
		sum=count=0;
		for(i=1; i<=n; i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		sort(e+1,e+n+1,cmp);
		for(i=1; i<=m; i++) f[i]=i;for(i=1; i<=n; i++) {if(merge(e[i].u,e[i].v)==1)
			{
				count++;
				sum+=e[i].w;
			}
			if(count==m- 1)
				break;
		}
		if(count==m- 1)
			printf("%d\n",sum);
		else
			printf("? \n");
	}
	return 0;
}
int getf(int u)
{
	if(u==f[u])
		return u;
	f[u]=getf(f[u]);
	return f[u];
}
int merge(int u,int v)
{
	u=getf(u);
	v=getf(v);
	if(u! =v) { f[v]=u;return 1;
	}
	return 0;
}
int cmp(struct data x,struct data y)
{
	return x.w<y.w;
}
Copy the code