In order to prepare the \The First National ACM School Contest" (in 20??) the major of the citydecided to provide all the schools with a reliable source of power. (The major is really afraid ofblackoutsJ). 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 betweensome schools. The major has decided to pick out two the cheapest connection plans { the cost of theconnection is equal to the sum of the connections between the schools. Your task is to help the major| nd 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. ThenTtest cases follow. The rst 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, andMthe number of possible connections among them. NextMlines contain three numbersAi,Bi,Ci, whereCiis the cost of the connection (1<Ci<300) betweenschoolsAiandBi. The schools are numbered with integers in the range 1 toN.
Output
For every test case print only one line of output. This line should contain two numbers separated by asingle space { the cost of two the cheapest connection plans. LetS1be the cheapest cost andS2thenext cheapest cost. It's important, thatS1=S2if and only if there are two cheapest plans, otherwiseS1<S2. You can assume that it is always possible to nd the costsS1andS2.
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
题目要求求出最小生成树和次小生成树。
首先要熟练最小生成树的求法，将最小生成树求出，再求次小生成树。
次小生成树是在最小生成树的基础上，遍历每一个没有入队的“一个”边入队，之后将最小生成树的队伍重置，在有一个之前没有入队的边入队的情况下，再次使用求最小生成树的方法求出次小生成树。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[10001],book[10001];struct bu
{int i,j,k;
}e[110*100];bool cmp(bu x,bu y)
{return x.k<y.k;
}int getf(int x)
{while(x!=a[x]){a[x]=a[a[x]];x=a[x];}return x;
}int merge(int x,int y)
{int tx=getf(x);int ty=getf(y);if(tx!=ty){a[ty]=tx;return 1;}return 0;
}void kruskal(int n,int m)
{memset(book,0,sizeof(book));//memset(a,0,sizeof(a));for(int i=1;i<=n;i++)a[i]=i;int ans=0,count=0;for(int i=1;i<=m;i++){if(merge(e[i].i,e[i].j)){book[i]=1;ans+=e[i].k;count++;}if(count==n-1)break;}printf("%d ",ans);//求出最小生成树ans=0;count=0;int minn=99999999;for(int i=1;i<=m;i++)//遍历没有入队的边{if(book[i]==0)//将之前没有入队的边入队{//memset(a,0,sizeof(a));for(int i=1;i<=n;i++)a[i]=i;merge(e[i].i,e[i].j);ans=e[i].k;count=1;for(int j=1;j<=m;j++){if(merge(e[j].i,e[j].j)){ans+=e[j].k;count++;}if(count==n-1)break;}minn=min(ans,minn);//遍历中最小的数即为次小生成树}}printf("%d\n",minn);}int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&e[i].i,&e[i].j,&e[i].k);}sort(e+1,e+m+1,cmp);//for(int i=1;i<=m;i++)// printf("%d %d %d\n",e[i].i,e[i].j,e[i].k);kruskal(n,m);}
return 0;}