UVA 10600 ACM Contest and Blackout(次小生成树)

#include <bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
int Map[maxn][maxn], path[maxn][maxn];
bool vis[maxn], used[maxn][maxn];
int dist[maxn], pre[maxn];
int T,n,m;

void init(){
  memset(used, false, sizeof(used));
  memset(path, 0, sizeof(path));
  memset(Map, inf, sizeof(Map));
}

int Prim(){
  memset(vis, false, sizeof(vis));
  int sum = 0;
  for(int i=1;i<=n;i++){
    dist[i] = Map[1][i];
    pre[i] = 1;
  }
  vis[1] = true;
  for(int i=1;i<n;i++){
    int Min = inf;
    int u = 1;
    for(int j=1;j<=n;j++){
      if(!vis[j] && dist[j] < Min){
        Min = dist[j];
        u = j;
      }
    }
    vis[u] = true;
    sum += Min;
    used[ u ][ pre[u] ] = used[ pre[u] ][ u ] = true;
    for(int j=1;j<=n;j++){
      if(vis[j] && j != u)
        path[j][u] = path[u][j] = max(path[j][pre[u]], dist[u]);
      if(vis[j] == false){
        if(dist[j] > Map[u][j]){
          dist[j] = Map[u][j];
          pre[j] = u;
        }
      }
    }
  }
  return sum;
}

int SecPrim(int xx){
  int ans = inf;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(i != j && used[i][j] == false){
        ans = min(ans, xx - path[i][j] + Map[i][j]);
      }
    }
  }
  return ans;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    init();
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
      int u, v, w;
      scanf("%d%d%d",&u,&v,&w);
      Map[u][v] = Map[v][u] = w;
    }
    int ans = Prim();
    int ans1 = SecPrim(ans);
    printf("%d %d\n", ans, ans1);
  }
  return 0;
}