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
题目大意：求一个图的最小生成树和次小生成树的权重？
思路：最小生成树就不用说了，直接一遍Dijkstra就可以，求次小生成树可以由删掉最小生成树的一条边来实现，这里n<100,直接枚举删边就好。
code:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f struct node { int x,y,w; }a[10010]; int f[120],q[120]; int n,m,ans1,ans2,tot; bool cmp(node aa,node bb) { return aa.w<bb.w; } int find(int x) { if(f[x] != x) f[x] = find(f[x]); return f[x]; } void dij() { ans1 = 0; for(int i=1;i<=n;i++) f[i] = i; for(int i=1;i<=m;i++) { int fx = find(a[i].x); int fy = find(a[i].y); if(fx != fy) { f[fy] =fx; ans1 += a[i].w; q[++tot] = i; } } } void dij1(int st) { int sum = 0,tt = 0; for(int i=1;i<=n;i++) f[i] = i; for(int i=1;i<=m;i++) if(i != st) { int fx = find(a[i].x); int fy = find(a[i].y); if(fx != fy) { f[fy] =fx; sum += a[i].w; tt++; } } if(tt == n-1) ans2 = min(ans2,sum); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); sort(a+1,a+1+m,cmp); tot = 0; dij(); ans2 = INF; for(int i=1;i<=tot;i++) dij1(q[i]); printf("%d %d\n",ans1,ans2); } return 0; }