POJ1679：The Unique MST（最小生成树）

The Unique MST

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 38430		Accepted: 14045

题目链接：http://poj.org/problem?id=1679

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:

Sample Output:

3

Not Unique!

题意：

判断最小生成树是否唯一，如果是就输出最小生成树的边权和。

题解：

对于权值相同的边，先把不能加入的边去除掉，然后把能加的边都加进图中，如果还剩有边，那么说明最小生成树不是唯一的。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

typedef long long ll;

const int N = ;

int t,n,m;

struct Edge{

    int u,v,w;

    bool operator < (const Edge &A)const{

        return w<A.w;

    }

}e[N*N];

int f[N];

int find(int x){

    return f[x]==x?f[x]:f[x]=find(f[x]);

}

int Kruskal(){

    int ans=,cnt,j;

    for(int i=;i<=n+;i++) f[i]=i;

    for(int i=;i<=m;i++){

        j=i;cnt=;

        while(e[i].w==e[j].w && j<=m) j++,cnt++;

        for(int k=i;k<j;k++){

            int fx=find(e[k].u),fy=find(e[k].v);

            if(fx==fy) cnt--;

        }

        for(int k=i;k<j;k++){

            int fx=find(e[k].u),fy=find(e[k].v);

            if(fx!=fy){

                f[fx]=fy;

                ans+=e[i].w;

                cnt--;

            }

        }

        if(cnt>) return -;

    }

    return ans ;

}

int main(){

    cin>>t;

    while(t--){

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            e[i].u=u;e[i].v=v;e[i].w=w;

        }

        sort(e+,e+m+);

        int ans = Kruskal();

        if(ans==-) puts("Not Unique!");

        else printf("%d\n",ans);

    }

    return ;

}

巴特西

POJ1679：The Unique MST（最小生成树）

最新文章

热门文章