# Minimum spanning tree - smooth engineering

Description
The goal of the provincial government's "unblocking project" is to make highway traffic possible between any two villages in the province (but there is not necessarily a direct highway connection, as long as it can be reached indirectly through the highway). After investigation and evaluation, the cost of several roads that may be constructed is listed in the statistical table. Now, please write a program to calculate the lowest cost for the smooth flow of the whole province.

Input
The test input contains several test cases. The first line of each test case shows the number of evaluated roads N, the number of villages m (< 100); the next N
Rows correspond to the cost of roads between villages. Each row gives a pair of positive integers, which are the number of two villages and the cost of roads between the two villages (also positive integers). For simplicity, villages are numbered from 1 to M. When N is 0, all inputs are ended and the corresponding results are not output.

Output
For each test case, output the lowest cost required for smooth operation of the whole province in one line. If the statistics are not enough to ensure smooth flow, output "?".

Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

Sample Output
3
?

```/*   Kruskar algorithm  */
/*The following conditions are met:
Use a structure to save the value of each pass and two nodes, and sort the passes from small to large,
Then judge whether the two points are in the same set in turn. If they are, do not perform the operation,
If not, execute N-1 to complete a minimum spanning tree
m Just connect m-1 edges with points
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int F[1001];
struct TREE
{
int b;
int e;
int p;
} t[1001];
bool cmp(struct TREE x,struct TREE y)
{
return x.p<y.p;
}
int find(int x)
{
if(x!=F[x])
F[x]=find(F[x]);
return F[x];
}
void U(int x,int y)
{
int root1,root2;
root1=find(x);
root2=find(y);
if(root1!=root2)
F[root2]=root1;
}
int main()
{
int n,m,i,j,ans=0,num=0;
int root1,root2;
while(scanf("%d %d",&n,&m)&&n!=0)
{
num=0;
ans=0;
for(i=1; i<=m; i++)
{
F[i]=i;
}
for(i=0; i<n; i++)
scanf("%d %d %d",&t[i].b,&t[i].e,&t[i].p);
sort(t,t+n,cmp);
for(i=0; i<n; i++)
{
root1=find(t[i].b);
root2=find(t[i].e);
if(root1!=root2)
{
ans+=t[i].p;
U(t[i].b,t[i].e);
num++;
}
}
if(num==m-1)
printf("%d\n",ans);
else
printf("?\n");

}
}
```

Posted on Thu, 13 Feb 2020 09:47:35 -0800 by camoconnell.com