POJ - The Unique MST(次小生成树)

题目链接:http://poj.org/problem?id=1679
Time Limit: 1000MS Memory Limit: 10000K

Description

Given a connected undirected graph, tell if its minimum spanning tree is unique. 

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties: 
1. V' = V. 
2. T is connected and acyclic. 

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'. 

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

Sample Input

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!

Problem solving report:

Description: 给一个图，问其最小生成树是否惟一。
Problem solving: 判断最小生成树是不是唯一的，我们求出次小生成树，和最小生成树比较即可。而次小生成树可由最小生成树换一条边得到。
我们要找次小生成树，一定是每次把不在最小生成树中的边加入一条并把最小生成树中的边删除一条，然后取所有非最小生成树中最小的，即次小生成树。
我们可以先用prim求出最小生成树T，在prim的同时，用一个矩阵Max[i][j]记录在树中连接i-j的路径中权值最大的边。然后枚举所有不在T中的边i-j，加入边i-j，如果加入的边和删除的边的大小是一样的，说明次小生成树的权值和等于最小生成树的权值和，也就是说最小生成树不唯一。

Accepted Code:

//Prim
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int inf = 0x3f3f3f3f;
bool vis[MAXN],visp[MAXN][MAXN];
int dis[MAXN], pre[MAXN], mp[MAXN][MAXN], Max[MAXN][MAXN];
struct edge {
    int v, w;
    edge() {}
    edge(int v, int w) : v(v), w(w) {}
    bool operator < (const edge &s) const {
        return s.w < w;
    }
};
int prim(int s, int n) {
    priority_queue <edge> Q;
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
        dis[i] = inf;
    }
    dis[s] = 0;
    Q.push(edge(s, dis[s]));
    int ans = 0;
    while (!Q.empty()) {
        edge u = Q.top();
        Q.pop();
        if (vis[u.v])
            continue;
        vis[u.v] = 1;
        ans += u.w;
        visp[u.v][pre[u.v]] = visp[pre[u.v]][u.v] = true;
        for (int j = 1; j <= n; j++) {
            if (vis[j])
                Max[u.v][j] = Max[j][u.v] = max(Max[j][pre[u.v]], dis[u.v]);
            if (!vis[j] && dis[j] > mp[u.v][j]) {
                pre[j] = u.v;
                dis[j] = mp[u.v][j];
                Q.push(edge(j, dis[j]));
            }
        }
    }
    return ans;
}
int MST(int n, int ans) {
    int min_ = inf;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (!visp[i][j] && mp[i][j] < inf)
                min_ = min(min_, ans + mp[i][j] - Max[i][j]);
    return min_;
}
int main() {
    int n, m, t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    mp[i][j] = inf;
        memset(pre, 0, sizeof(pre));
        memset(visp, 0, sizeof(visp));
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            mp[u][v] = mp[v][u] = w;
        }
        int ans = prim(1, n);
        if (ans != MST(n, ans))
            printf("%d\n", ans);
        else printf("Not Unique!\n");
    }
    return 0;
}

//Kruskal
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXM = MAXN * MAXN;
const int inf = 0x3f3f3f3f;
bool vis[MAXN];
int Max[MAXN][MAXN];
struct edge {
    int u, v, w;
    bool operator < (const edge &s) const {
        return s.w > w;
    }
}e[MAXM];
int f[MAXN];
vector <int> G[MAXN];
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
int getf(int v) {
    if (f[v] != v)
        return f[v] = getf(f[v]);
    return v;
}
bool merge(int u, int v, int w) {
    int t1 = getf(u);
    int t2 = getf(v);
    if (t1 != t2) {
        f[t1] = t2;
        int siz1 = G[t1].size(), siz2 = G[t2].size();
        for (int j = 0; j < siz1; j++)
            for (int k = 0; k < siz2; k++)
                Max[G[t1][j]][G[t2][k]] = Max[G[t2][k]][G[t1][j]] = w;
        for (int j = 0; j < siz1; j++)
            G[t2].push_back(G[t1][j]);
        return true;
    }
    return false;
}
int Kruskal(int n, int m) {  
    int cnt = 0, count_ = 0;
    for (int i = 1; i <= n; i++) {
        G[i].clear();
        G[i].push_back(i);
        f[i] = i;
    }
    sort(e, e + m);
    for (int i = 0; i < m && count_ < n - 1; i++) {
        if (merge(e[i].u, e[i].v, e[i].w)) {
            count_++;
            cnt += e[i].w;
            vis[i] = true;
        }
    }
    return cnt;
}
int MST(int m, int ans) {
    int min_ = inf;
    for (int i = 0; i < m; i++)
        if (!vis[i])
            min_ = min(min_, ans + e[i].w - Max[e[i].u][e[i].v]);
    return min_;
}
int main() {
    int n, m, t;
    scanf("%d", &t);
    while (t--) {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        int ans = Kruskal(n, m);
        if (ans != MST(m, ans))
            printf("%d\n", ans);
        else printf("Not Unique!\n");
    }
    return 0;
}