不严格次小生成树。

注意图可能不连通。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 505; const int INF = 1e7; bool vis[maxn]; int d[maxn]; int pre[maxn]; int Max[maxn][maxn]; int g[maxn][maxn]; int n, m; void init() { int u, v, c; scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) g[i][j] = INF; for(int i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); g[u][v] = g[v][u] = c; } } int Prim() { for(int i=2; i<=n; ++i) { pre[i]=1; d[i] = g[1][i]; } memset(vis, 0, sizeof vis ); vis[1] = 1; d[1] = 0; pre[1] = -1; int ans = 0; for(int i=1; i
      
       d[j]){ Mn = d[k=j];} if(-1==k) return INF; ans += Mn; g[k][pre[k]] = g[pre[k]][k] = INF; for(int j=1; j<=n; ++j) if(vis[j]) Max[j][k] = Max[k][j] = max(Mn, Max[pre[k]][j]); vis[k] = 1; for(int j=1; j<=n; ++j) if(!vis[j]&&d[j]>g[j][k]) { d[j] = g[j][k]; pre[j] = k; } } return ans; } void solve() { int ans1 = Prim(); if(ans1==INF) { printf("Cost: -1\n"); } else { printf("Cost: %d\n", ans1); } int ans2 = INF; for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j) if(g[i][j]!=INF) { ans2 = min(ans2, ans1+g[i][j]-Max[i][j]); } if(ans2==INF){ printf("Cost: -1\n"); } else { printf("Cost: %d\n", ans2); } } int main() { init(); solve(); return 0; }