POJ1679 The Unique MST（次小生成树）

题目链接

题意：判断最小生成树是否唯一。

可以通过求次小生成树解决，如果相等则说明不唯一。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;
int cost[MAXN][MAXN];
bool vis[MAXN];
int lowc[MAXN];
int pre[MAXN];
int Max[MAXN][MAXN];
bool used[MAXN][MAXN];

int Prim(int cost[][MAXN], int n){
    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 < n; i++){
        lowc[i] = cost[0][i];
        pre[i] = 0;
    }
    lowc[0] = 0;
    for(int i = 1; i < n; i++){
        int minc = INF;
        int p = -1;
        for(int j = 0; j < n; j++){
            if(!vis[j] && minc>lowc[j]){
                minc = lowc[j];
                p = j;
            }
        }

        if(minc == INF)return -1;
        ans += minc;
        vis[p] = true;
        used[p][pre[p]] = used[pre[p]][p] = true;
        for(int j = 0; j < n; j++){
            if(vis[j]) Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);
            if(!vis[j] && lowc[j]>cost[p][j]){
                lowc[j] = cost[p][j];
                pre[j] = p;
            }
        }
    }
    return ans;
}
int ans;
int smst(int cost[][MAXN],int n){
    int Min = INF;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(cost[i][j]!=INF && !used[i][j]){
                Min = min(Min, ans+cost[i][j]-Max[i][j]);
            }
    if(Min == INF) return -1;
    return Min;
}

int main(){
//    freopen("a.txt", "r", stdin);
    int t,m,n;
    cin >> t;
    while(t--){
        scanf("%d%d", &n, &m);
        memset(cost, 0x3f, sizeof(cost));
        int a, b, c;
        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &a, &b, &c);
            a--; b--;
            cost[a][b] = cost[b][a] = c;
        }
        ans = Prim(cost, n);
        int ci = smst(cost, n);
        if(ans != ci) cout << ans << endl;
        else cout << "Not Unique!" <<endl;
    }
    return 0;
}