题目链接：https://vjudge.net/problem/UVA-10600
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
题解：
赤裸裸的求最小生成树和次小生成树。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 typedef long long LL; 7 const double EPS = 1e-6; 8 const int INF = 2e9; 9 const LL LNF = 9e18; 10 const int MOD = 1e9+7; 11 const int MAXN = 1e2+10; 12 13 int cost[MAXN][MAXN], lowc[MAXN], pre[MAXN], Max[MAXN][MAXN]; 14 bool vis[MAXN], used[MAXN][MAXN]; 15 16 int Prim(int st, int n) 17 { 18 int ret = 0; 19 memset(vis, false, sizeof(vis)); 20 memset(used, false, sizeof(used)); 21 memset(Max, 0, sizeof(Max)); 22 23 for(int i = 1; i<=n; i++) 24 lowc[i] = (i==st)?0:INF; 25 pre[st] = st; 26 27 for(int i = 1; i<=n; i++) 28 { 29 int k, minn = INF; 30 for(int j = 1; j<=n; j++) 31 if(!vis[j] && minn>lowc[j]) 32 minn = lowc[k=j]; 33 34 vis[k] = true; 35 ret += minn; 36 used[pre[k]][k] = used[k][pre[k]] = true; //pre[k]-k的边加入生成树 37 for(int j = 1; j<=n; j++) 38 { 39 if(vis[j] && j!=k) //如果遇到已经加入生成树的点，则找到两点间路径上的最大权值。 40 Max[j][k] = Max[k][j] = max(Max[j][pre[k]], lowc[k]); //k的上一个点是pre[k] 41 if(!vis[j] && lowc[j]>cost[k][j]) //否则，进行松弛操作 42 { 43 lowc[j] = cost[k][j]; 44 pre[j] = k; 45 } 46 } 47 } 48 return (ret==INF)?-1:ret; 49 } 50 51 int SMST(int t1 ,int n) 52 { 53 int ret = INF; 54 for(int i = 1; i<=n; i++) //用生成树之外的一条边去代替生成树内的一条边 55 for(int j = i+1; j<=n; j++) 56 { 57 if(cost[i][j]!=INF && !used[i][j]) //去掉了i-j路径上的某条边，但又把i、j直接连上，所以还是一棵生成树。 58 ret = min(ret, t1+cost[i][j]-Max[i][j]); 59 } 60 return ret; 61 } 62 63 int main() 64 { 65 int T, n, m; 66 scanf("%d", &T); 67 while(T--) 68 { 69 scanf("%d%d",&n,&m); 70 for(int i = 1; i<=n; i++) 71 for(int j = 1; j<=n; j++) 72 cost[i][j] = (i==j)?0:INF; 73 74 for(int i = 1; i<=m; i++) 75 { 76 int u, v, w; 77 scanf("%d%d%d", &u, &v, &w); 78 cost[u][v] = cost[v][u] = w; 79 } 80 81 int t1 = Prim(1, n); 82 int t2 = SMST(t1, n); 83 printf("%d %d ", t1, t2); 84 } 85 }