POJ 1679-The Unique MST（最小生成树是否唯一）

电玩女神 2022-09-24 12:27 131阅读 0赞

The Unique MST

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;27088</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9691</td> 
  </tr> 
 </tbody> 
</table>

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!

Source

[POJ Monthly--2004.06.27 srbga@POJ][POJ Monthly--2004.06.27 srbga_POJ]

## 题目意思： ##

求最小生成树是否唯一。

## 解题思路： ##

①对图中每条边，扫描其他边，如果存在相同权值的边，则对该边做标记；

②然后用Kruskal（或Prim）算法求MST；

③求得MST后，

如果该MST中未包含做了标记的边，即可判定MST唯一；

如果该MST中包含做了标记的边，，则依次去掉这些边再求MST，如果求得的MST权值与原MST权值相同，则判定MST不唯一。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define MAXN 1010
    #define INF 0xfffffff//0X代表16进制，后面是数字，十进制是4294967295
    using namespace std;
    int cost[MAXN][MAXN],dis[MAXN],pre[MAXN];
    int n,m;
    int V,E;//顶点数和边数
    bool first;
    
    struct edge
    {
        int u,v,cost;
        bool eq;//标记边长是否相等
        bool used;//标记第一次是否使用过
        bool del;//标记判断最小生成树是否唯一时，依次去掉的边
    };
    edge es[MAXN];
    
    bool cmp(const edge &e1,const edge &e2)
    {
        return e1.cost<e2.cost;
    }
    
    
    int set_find(int x)
    {
        while(x!=pre[x])
            x=pre[x];
        return x;
    }
    
    bool unite(int p,int q)
    {
        p=set_find(p);
        q=set_find(q);
        if(p!=q)
        {
            pre[p]=q;
            return true;
        }
        return false;
    }
    
    bool same(int x,int y)
    {
        return set_find(x)==set_find(y);
    }
    
    void init_union_find(int n)
    {
        for(int i=0; i<=n; i++)
            pre[i]=i;
    }
    
    int kruskal()
    {
        sort(es,es+m,cmp);//按照edge.cost的顺序升序排列
        init_union_find(V);//并查集初始化
        int res=0;
        for(int i=0; i<m; ++i)
        {
            if(es[i].del==true) continue;
            edge e=es[i];
            if(!same(e.u,e.v))//不是圈
            {
                unite(e.u,e.v);
                if(first) es[i].used=true;//标记第一次生成树的时候是否用过该边
                res+=e.cost;//累加最小生成树的长度
                //Max=max(Max,e.cost);
            }
        }
        return res;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            memset(dis,0,sizeof(dis));
            memset(es,0,sizeof(edge)*MAXN);//注意一定要初始化清空
            for(int i=0; i<m; i++)
                cin>>es[i].u>>es[i].v>>es[i].cost;
            for(int i=0; i<m; i++)
                for(int j=0; j<m; j++)
                {
                    if(i==j) continue;
                    if(es[j].cost==es[i].cost)//标记权值相同的边
                        es[j].eq=true;
                }
            V=n;
            E=n*n;
            first=true;//是否是第一次生成MST
            int ans1=kruskal(),i;
            first=false;
            for(i=0; i<m; i++)//依次去掉原MST中权值相同的边
            {
                if(es[i].used&&es[i].eq)//如果第一棵MST中包含了被标记的边
                {
                    es[i].del=true;
                    int ans2=kruskal();//第二棵MST
                    if(ans1==ans2)//两棵生成树权值相同，则不唯一
                    {
                        cout<<"Not Unique!"<<endl;
                        break;
                    }
                    es[i].del=false;
                }
            }
            if(i>=m) cout<<ans1<<endl;//MST唯一
        }
        return 0;
    }
    /*
    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
    
    */

[POJ Monthly--2004.06.27 srbga_POJ]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2004.06.27+srbga%40POJ