首页 > 代码库 > poj1679 The Unique MST

poj1679 The Unique MST

2024-07-16 22:39:05   220人阅读

  题目大意:给定一个联无向网，判断它的最小生成树是否唯一。
  
The Unique MST
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 20421
Accepted: 7183

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!


1：在prim()中记录每个入树点的前缀点，在一次prim（）之后对每个入树点a  遍历其它所有的入树点，
   看该入树点a的入树方式是否唯一，若不唯一，则存在多个最小生成树！.

<span style="font-size:18px;">#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<vector>
using namespace std;
#define maxn 150
#define MM 100000000
int n,m,sum;
int v[maxn];
int d[maxn];
int W[maxn][maxn];
int w[maxn][maxn];
int vis[maxn];
int Vis[maxn][maxn];
int conut;
void prim()
{
     sum=0;
     memset(v,0,sizeof(v));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        d[i]=(i==1?0:MM);
    for(int j=1;j<=n;j++)
    {
        int x,mm=MM;
        for(int i=1;i<=n;i++)
        if(d[i]<mm && !v[i])
        mm=d[x=i];
        sum+=mm;
        v[x]=1;
        for(int i=1;i<=n;i++)
            if(d[i]>w[x][i])
            {

               d[i]=w[x][i];
               vis[i]=x;
            }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        conut=0;
        int a,b,c;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
             w[i][j]=MM;
        for(int i=1;i<=m;i++)
        {
             scanf("%d%d%d",&a,&b,&c);
             if(w[a][b]>c)
                w[a][b]=w[b][a]=c;
        }
        prim();
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
            for(int j=1;j<=n;j++)
            if(j!=vis[i] && v[j] && w[j][i]==w[i][vis[i]])
            conut=1;
        }

        if(conut)
         printf("Not Unique!\n");
         else
            printf("%d\n",sum);
    }
    return 0;
}
</span>

******************####################################################**********************
  
2：逐个删边再次prim（）；容易想到，复杂度高O(n^4)    在每个点入树的时候用数组vis标记改点的入树“支点”。----这是   我做这题时不知道怎么处理的地方。
<span style="font-size:18px;">  #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<vector>
    using namespace std;
    #define maxn 150
    #define MM 100000000
    int n,m,sum;
    int v[maxn];
    int d[maxn];
    int W[maxn][maxn];
    int w[maxn][maxn];
    int vis[maxn];
    int Vis[maxn][maxn];
    void prim()
    {
         sum=0;
         memset(v,0,sizeof(v));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            d[i]=(i==1?0:MM);
        for(int j=1;j<=n;j++)
        {
            int x,mm=MM;
            for(int i=1;i<=n;i++)
                if(d[i]<mm && !v[i])
                mm=d[x=i];
                sum+=mm;
            v[x]=1;
            for(int i=1;i<=n;i++)
                if(d[i]>w[x][i])
                {
                     d[i]=w[x][i];
                    vis[i]=x;        //  保存入树点的入树“支点”
                }
        }
    }
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            int a,b,c;
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                 w[i][j]=MM;
            for(int i=1;i<=m;i++)
            {
                 scanf("%d%d%d",&a,&b,&c);
                 if(w[a][b]>c)
                    w[a][b]=w[b][a]=c;     
            }
            prim();
            memset(Vis,0,sizeof(Vis));
           for(int i=n;i>1;i--)
           {
               if(vis[i])
                Vis[vis[i]][i]=Vis[i][vis[i]]=1;   // 标记入树的边
           }
           for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            W[i][j]=w[i][j];                     //用W数组保存各边的原始数据，Sum保存最小的距离，conut标记是否有不止一个最小生成树。
            int SUM=sum,conut=0,cc=0; 
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                if(Vis[i][j]==1)            //如果该边在第一次prim中已入树，删除该边，再次prim();
             {
                if(conut)
                    break;
                 for(int ii=1;ii<=n;ii++)
                for(int jj=1;jj<=n;jj++)
                w[ii][jj]=W[ii][jj];
                w[i][j]=w[j][i]=MM;
                prim();
                if(SUM==sum)             // 一旦删除边后所求最小生成树与删除边前所求相等 ----最小生成树不唯一。conut=1;
                {
                    conut=1;            //还可以 用conut++ 来求最小生成树的个数。
                }
            }
                if(!conut)
                printf("%d\n",SUM);
                else
                printf("Not Unique!\n");

        }
        return 0;
}</span>


联系
我们