K - The Unique MST——判断一个连通无向图的最小生成树是否是唯一的

秒速五厘米 2022-06-11 08:06 170阅读 0赞

字节跳动校招内推码: C4BDSMC
    投递链接: https://job.toutiao.com/s/J691fRK
    内推交流QQ群：1049175720

Think:  
1知识点：判断一个连通无向图的最小生成树是否是唯一的+最小生成树\_Prim算法+记录路径  
2题意：给定一个连通无向图，判断这个连通无向图的最小生成树是否是唯一的  
3错误反思：  
4思路：  
1>思路1：第一遍Prim算法求出路径最小权值和且记录路径，然后逐一试探删掉一条记录的路径之后图是否连通，若图连通则判断当前状态最小生成树最小边权和是否和之前的最小权值和相等，逐一遍历完成后若无最小边权和等于第一遍Prim算法求出的最小权值和，则说明最小生成树唯一，反之则说明最小生成树不唯一  
2>思路2：通过Kruskal算法构建最小生成树，第一次构建时标记构建边，之后类似思路1逐一试探每一条边的影响，若存在次小生成树最小权值和等于最小生成树权值和则说明最小生成树不唯一，反之则说明最小生成树唯一

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——思路1Prim算法——暂未找到错误所在

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 114;
    
    struct Edge{
        int u, v, w;
    }link[5014];
    
    int tp, vis[N], dis[N], path[N], e[N][N];
    
    void Prim(int n);
    
    int main(){
        int T, n, m, i, u, v, w;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(e, inf, sizeof(e));
            for(i = 0; i < n; i++){
                scanf("%d %d %d", &u, &v, &w);
                if(w < e[u][v])
                    e[u][v] = e[v][u] = w;
            }
            Prim(n);
        }
        return 0;
    }
    void Prim(int n){
        int i, miv, v, num, ans, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++){
            dis[i] = e[1][i];
            path[i] = 1;
        }
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        tp = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            if(miv == inf){
                printf("Not Unique!\n");
                return;
            }
            vis[v] = 1, num++, sum += miv;
            link[tp].u = path[v], link[tp].v = v, link[tp].w = e[path[v]][v], tp++;
            for(i = 1; i <= n; i++){
                if(!vis[i] && e[v][i] < dis[i]){
                    dis[i] = e[v][i];
                    path[i] = v;
                }
            }
        }
        ans = sum;
        for(int k = 0; k < tp; k++){
            int x = link[k].u;
            int y = link[k].v;
            int z = link[k].w;
            e[x][y] = e[y][x] = inf;
            memset(vis, 0, sizeof(vis));
            for(i = 1; i <= n; i++)
                dis[i] = e[1][i];
            vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
            while(num < n){
                miv = inf;
                for(i = 1; i <= n; i++){
                    if(!vis[i] && dis[i] < miv){
                        miv = dis[i], v = i;
                    }
                }
                if(miv == inf)
                    break;
                vis[v] = 1, num++, sum += miv;
                for(i = 1; i <= n; i++){
                    if(!vis[i] && e[v][i] < dis[i])
                        dis[i] = e[v][i];
                }
            }
            if(num == n && sum == ans){
                printf("Not Unique!\n");
                return;
            }
            e[x][y] = e[y][x] = z;
        }
        printf("%d\n", ans);
    }

以下为Accepted代码——思路2Kruskal算法

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 114;
    
    struct Edge{
        int x, y, w;
        int flag;
        bool operator < (const Edge &b) const{
            return w < b.w;
        }
    }edge[5014];
    
    int n, f[N];
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    int Kruskal(int num, int m);
    
    int main(){
        int T, m, i, sum, ans, cnt;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            Init(n);
            for(i = 0; i < m; i++){
                scanf("%d %d %d", &edge[i].x, &edge[i].y, &edge[i].w);
                edge[i].flag = 0;
            }
            sort(edge, edge+m);
            cnt = 1, ans = 0;
            for(i = 0; i < m; i++){
                if(Merge(edge[i].x, edge[i].y)){
                    edge[i].flag = 1;
                    ans += edge[i].w;
                    cnt++;
                }
            }
            int flag = 0;
            for(i = 0; i < m; i++){
                if(edge[i].flag == 1){
                    sum = 0;
                    Init(n);
                    sum = Kruskal(i, m);
                    if(sum == ans){
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag) printf("Not Unique!\n");
            else printf("%d\n", ans);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 0; i <= n; i++)
            f[i] = i;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            return false;
        else {
            f[t2] = t1;
            return true;
        }
    }
    int Kruskal(int num, int m){
        int i;
        int ans = 0, cnt = 1;
        for(i = 0; i < m; i++){
            if(i != num){
                if(Merge(edge[i].x, edge[i].y)){
                    ans += edge[i].w;
                    cnt++;
                }
            }
        }
        if(cnt != n) return -1;
        else return ans;
    }

以下为Accepted代码——思路1Prim算法——参考前辈

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 114;
    
    int Map[N][N];/*邻接矩阵存图*/
    int Max[N][N];/*记录最小生成树中i到j的最大边权*/
    bool used[N][N];/*记录当前边是否加入最小生成树*/
    int path[N];/*记录当前下标路的起点*/
    int vis[N], dis[N];
    
    void Init(int n);/*初始化*/
    void Read(int m);/*读入输入数据*/
    int Prim(int n);/*最小生成树Prim算法*/
    int smst(int n, int min_ans);/*次小生成树*/
    void solve(int n);/*判断图的最小生成树是否唯一*/
    
    int main(){
        int T, n, m;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            Init(n);
            Read(m);
            solve(n);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++){
            Map[i][i] = 0;
            for(int j = i+1; j <= n; j++){
                Map[i][j] = Map[j][i] = inf;
            }
        }
    }
    void Read(int m){
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            Map[u][v] = Map[v][u] = w;
        }
    }
    int Prim(int n){
        int i, miv, v, num, sum;
        memset(vis, 0, sizeof(vis));
        memset(used, false, sizeof(used));
        memset(Max, 0, sizeof(Max));
        for(int i = 1; i <= n; i++){
            dis[i] = Map[1][i];
            path[i] = 1;
        }
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            if(miv == inf) return -1;
            vis[v] = 1, num++, sum += miv;
            used[path[v]][v] = used[v][path[v]] = true;
            for(i = 1; i <= n; i++){
                if(vis[i])
                    Max[i][v] = Max[v][i] = max(Max[i][path[v]], dis[v]);
                if(!vis[i] && Map[v][i] < dis[i]){
                    dis[i] = Map[v][i];
                    path[i] = v;
                }
            }
        }
        return sum;
    }
    void solve(int n){
        int ans = Prim(n);
        if(ans == -1){
            printf("Not Unique!\n");
            return;
        }
        if(smst(n, ans) == ans)
            printf("Not Unique!\n");
        else
            printf("%d\n", ans);
    }
    int smst(int n, int ans){
        int sum = inf;
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                if(Map[i][j] != inf && !used[i][j])
                    sum = min(sum, ans+Map[i][j]-Max[i][j]);
            }
        }
        if(sum == inf) return -1;
        return sum;
    }

[vjudge]: https://vjudge.net/contest/163010#problem/K