O - ACM contest and blackout (minimum spanning tree, Kruskal)

In order to prepare the “The First National ACM School Contest” (in 20??) the major of the city
decided to provide all the schools with a reliable source of power. (The major is really afraid of
blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one)
must be connected; in addition, some schools must be connected as well.
You may assume that a school has a reliable source of power if it’s connected directly to “Future”,
or to any other school that has a reliable source of power. You are given the cost of connection between
some schools. The major has decided to pick out two the cheapest connection plans – the cost of the
connection is equal to the sum of the connections between the schools. Your task is to help the major
— find the cost of the two cheapest connection plans.
Input
The Input starts with the number of test cases, T (1 < T < 15) on a line. Then T test cases follow. The
first line of every test case contains two numbers, which are separated by a space, N (3 < N < 100)
the number of schools in the city, and M the number of possible connections among them. Next M
lines contain three numbers Ai
, Bi
, Ci
, where Ci
is the cost of the connection (1 < Ci < 300) between
schools Ai and Bi
. The schools are numbered with integers in the range 1 to N.
Output
For every test case print only one line of output. This line should contain two numbers separated by a
single space – the cost of two the cheapest connection plans. Let S1 be the cheapest cost and S2 the
next cheapest cost. It’s important, that S1 = S2 if and only if there are two cheapest plans, otherwise
S1 < S2. You can assume that it is always possible to find the costs S1 and S2.
Sample Input
2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
Sample Output
110 121
37 37
The question ：
Find the smallest spanning tree , And sub minimum spanning tree ,
use kruskal Algorithm , Find the minimum number first , And mark each path ,
Then use the same method to find the secondary short circuit , The concrete is ： Remove one marked edge at a time , Then traverse , Find the shortest path at this time , Totally removed n-1 side , Traverse in turn to find the shortest path at that time , Finally, find the smallest one , It's a short circuit

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=888;
int MAX=0x3f3f3f3f;
int n,m;
int dist[N],map[N][N];
int biao[N];
int sum[N];
int x[N],y[N];
int mm[N];
int pre[N];
struct node{
    
	int u,v,w;
}a[N*(N-1)/2];
bool cmp(node a,node b)
{
    
	return a.w<b.w;
}
int find(int x)
{
    
	if(pre[x]==x)
	return x;
	else
	return pre[x]=find(pre[x]);
}
int judge(int u,int v)
{
    
	int fx=find(u);
	int fy=find(v);
	if(fx!=fy)
	{
    
		pre[fx]=fy;
		return 1;
	}
	return 0;
}
void unit()
{
    
	for(int i=1;i<=n;i++)
	{
    
		pre[i]=i;
	}
}
int main()
{
    
   int t;
   cin>>t;
   while(t--)
   {
    
   	cin>>n>>m;
   	unit();// The root node of each point is itself 
   	memset(biao,0,sizeof(biao));
   	for(int i=0;i<m;i++)
   	{
    
   	  cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a,a+m,cmp);
	int ans=0,num=0;
	for(int i=0;i<m;i++)
	{
    
		if(judge(a[i].u,a[i].v))
		{
    
			ans+=a[i].w;
			num++;
			biao[i]=1;
			if(num==n-1)
			break;
		}
	}
	int minn=ans;
	int minnn=MAX;
	for(int i=0;i<m;i++)
	{
    
		ans=0,num=0;
		if(biao[i]==1)// Remove a marked edge 
		{
    
			unit();// Reinitialize 
			for(int j=0;j<m;j++)
			{
    
				if(i==j)
				continue;
		    if(judge(a[j].u,a[j].v))
	    	{
    
			ans+=a[j].w;
			num++;
			
			if(num==n-1)
			{
    
				minnn=min(minnn,ans);
					break;
			}
		
	    	}
			}
		}
	}
	   cout<<minn<<" "<<minnn<<endl;
   }
    return 0;
}