POJ 1679 The Unique MST(Prim)

Description

求最小生成树是否唯一

Analyze

可以求非严格次小生成树，看是否与最小生成树相同

用Prim做法，检测某个点到“已连接集合”的最小距离是否唯一

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;

int n, m, ans, mp[N][N], vis[N], low[N], cnt[N];

void Prim()
{
    ans = 0;
    int pos = 1, mmin = INF;
    memset(cnt,   0, sizeof(cnt));
    memset(vis,   0, sizeof(vis));
    memset(low, INF, sizeof(low));
    vis[1] = 1;
    for(int i = 1; i <= n; ++i)
        low[i] = mp[pos][i], cnt[i] = 1;

    int tot = n;
    while(--tot)
    {
        mmin = INF;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && low[i] < mmin)
                mmin = low[i], pos = i;
        ///if(mmin == INF)
        vis[pos] = 1;
        ans += mmin;
        for(int i = 1; i <= n; ++i)
            if(!vis[i])
            {
                if(low[i] == mp[pos][i])
                    cnt[i]++;
                else if(low[i] > mp[pos][i])
                    low[i] = mp[pos][i], cnt[i] = 1;
            }
    }
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                mp[i][j] = (i == j ? 0 : INF);
        int u, v, w;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d %d", &u, &v, &w);
            mp[u][v] = mp[v][u] = w;
        }
        Prim();
        bool flag = 0;
        for(int i = 1; i <= n; ++i)
            if(cnt[i] > 1)
            {
                flag = 1;
                break;
            }
        if(flag)
            cout << "Not Unique!" << '\n';
        else
            cout << ans << '\n';
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73