POJ 1679：The Unique MST（次小生成树&&Kruskal）[通俗易懂]

Description

Input

Output

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!

这道题就是要你推断是否为唯一的最小生成树。。

这也是我第一道次小生成树的题。。那个PDF资料真是太好了。。我用的是Kruskal。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

const int max1 = 105;
const int max2 = 10005;

struct node
{
    int u, v, w;//边的顶点以及权值
    int r;//用于记录边的序号
    int used;//用于记录边是否被使用过
}edge[max2];//边的数组

int parent[max1];//顶点i所在集合相应树中的根节点
int n, m;//顶点数，边的个数
int cas;

void start()//初始化
{
    for(int i=1; i<=n; i++)
        parent[i] = i;
}

int find (int x)//查找并返回节点x所属集合的根节点
{
    return parent[x] == x ?
 x : parent[x] = find ( parent[x] );}bool cmp ( node a, node b )//按权值从小到大排序{    return a.w < b.w;}int Kruskal()//第一次求最小生成树{    sort( edge+1, edge+m+1, cmp );    int ans = 0;    for(int i=1; i<=m; i++)    {        int e = edge[i].r;        int x = find( edge[i].u );        int y = find( edge[i].v );        if( x!=y )        {            parent[y] = x;            ans += edge[i].w;            edge[e].used = 1;        }    }    return ans;}int Kruskal_again(int tt)//求次小生成树{     sort( edge+1, edge+m+1, cmp );    int ans = 0;    for(int i=1; i<=m; i++)    {        if( tt==edge[i].r )            continue;        int x = find( edge[i].u );        int y = find( edge[i].v );        if( x!=y )        {            parent[y] = x;            ans += edge[i].w;        }    }    return ans;}bool judge()//推断是否能就得最小生成树，即看是否有孤立的点{    for(int i=1; i<=n; i++)        if( find(i) != find(1) )        return false;    return true;}int main(){    scanf("%d", &cas);    while( cas-- )    {        scanf("%d%d", &n, &m);        start();        for(int i=1; i<=m; i++)        {            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);            edge[i].used = 0;            edge[i].r = i;        }        int flag = 0;        int ans1 = Kruskal();        for(int i=1; i<=m; i++)//一一枚举求最小生成树。。        {            if( !edge[i].used )                continue;            start();            int ans2 = Kruskal_again(i);//求除去此边的最小生成树            if( ans1 == ans2 && judge() )            {                flag = 1;//标记结论                break;            }        }        if( flag )            printf("Not Unique!\n");        else            printf("%d\n", ans1);    }    return 0;}