poj 1679 The Unique MST，次小生成树

次小生成树
求最小生成树时，用数组Max[i][j]来表示MST中i到j的最大边权。
求完后，直接枚举所有不在MST中的边，替换掉最大边权的边，更新答案。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 110; const int INF = 1e9; bool vis[maxn]; int d[maxn]; int pre[maxn]; int Max[maxn][maxn]; bool used[maxn][maxn]; int g[maxn][maxn]; int n, m; int Prim() { int ans = 0; memset(vis, false, sizeof vis ); memset(Max, 0, sizeof Max ); memset(used, false, sizeof used ); vis[0] = true; pre[0] = -1; for(int i=1; i
     
      d[j])) p = j; if(-1==p) return -1; ans += d[p]; vis[p] = true; used[p][pre[p]] = used[pre[p]][p] = true; for(int j=0; j
      
       g[p][j]) { d[j] = g[p][j]; pre[j] = p; } } } return ans; } void solve() { int res = Prim(); if(-1 == res) { //图不连通 puts("Not Unique!"); return ; } int Mn = INF; for(int i=0; i