给出一个带权无向图，求出最小生成树和次小生成树，注意这里两个结果可以相等。当生成树不存在的时候就可以输出-1；
思路：
这是典型的次小生成树的求法，注意细节尤其是初始化。错了好多次。 次小生成树就是有一条边和最小生成树不一样。所以保存最小生成树的每一条边，然后遍历即可。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 505; const int INF = 0x3f3f3f3f; int used[MAX]; int f[MAX]; int n,m; int Minused; struct Edge { int s,e,v; }edge[MAX*MAX]; int cmp(Edge a,Edge b) { return a.v < b.v; } void init() { for(int i = 0;i <= n; i++) f[i] = i; } int Find(int x) { if(x != f[x]) f[x] = Find(f[x]); return f[x]; } int krustal() { init(); memset(used,0,sizeof(used)); sort(edge,edge+m,cmp); int pos = 0,flag = 0; Minused = 0; int ans = 0; for(int i = 0;i < m; i++) { int a = Find(edge[i].s); int b = Find(edge[i].e); if(a != b) { f[a] = b; pos++; used[Minused++] = i; ans += edge[i].v; } if(pos == n - 1) { break; } } if(pos == n - 1) return ans; return -1; } int Next_min_tree() { int temp = INF; for(int i = 0;i < Minused; i++) { init(); int pos = 0; int ans = 0; for(int j = 0;j < m; j++) { if(used[i] != j) { int a = Find(edge[j].s); int b = Find(edge[j].e); if(a != b) { f[a] = b; pos++; ans += edge[j].v; } if(pos == n -1) break; } } if(pos == n - 1 && temp > ans) temp = ans; } if(temp == INF) return -1; return temp; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF) { for(int i = 0;i < m; i++) { scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].v); } int ans = krustal(); int ans1 = Next_min_tree(); printf("Cost: %d\n",ans); printf("Cost: %d\n",ans1); } return 0; }