poj 1679 The Unique MST(kruskal)

解题思路

题意：

     给你一个连通无向图，看它的最小生成树是不是唯一的。

 

思路：

   先求出最小生成树T1，再在那棵树上删去一条边，再求最小生成树，看求出的那棵树的权是否跟T1的权一样，一样的话说明存在不止一颗，否则再删另一条边再找，直到T1的每条边都测过。

注意点有三：

1.    是删去一条边后，测完后要恢复那条边。

2.    如果是kruskal做的话要注意边权为0的情况，我WA了一次

3.    顶点最多有100个，所以边最多有100*99/2条，  我为此RE了三次，没看清题目啊~~

源程序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 103
#define M (N-1)*N/2
struct edge
{
    int x;
    int y;
    int w;
    int mark;
}edges[M];
int rank[N], pre[N], sum, sum1;

int cmp(const void *p, const void *q)
{
    return ((struct edge*)p)->w - ((struct edge *)q)->w;
}

int find(int x)
{
    int y, z;
    y = x;
    while(pre[y] != y)
    {
        y = pre[y];
    }
    while(x != y)
    {
        z = pre[x];
        pre[x] = y;
        x = z;
    }
    return y;
}

int count;
void _union(struct edge &e, int flag)
{
    int x, y;
    x = find(e.x);
    y = find(e.y);
    if(x != y)
    {
        if(flag == 2)
        {
            sum1 += e.w;
            count++;
        }
        else
        {
            sum += e.w;
            e.mark = 1;
        }
        if(rank[x] < rank[y])
        {
            pre[x] = y;
        }
        else
        {
            if(rank[x] == rank[y])
                rank[x]++;
            pre[y] = x;
        }
    }
}
int main()
{
    int i, j;
    int n,m, t, ok;
    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
            edges[i].mark = 0;
        }
        for(i=1; i<=n; i++)
        {
            rank[i] = 0;
            pre[i] = i;
        }
        qsort(edges+1, m, sizeof(edges[1]), cmp);
        sum = 0;
        for(i=1; i<=m; i++)
        {
            if(!edges[i].mark)
                _union(edges[i], 1);
        }
        ok = 0;
        for(i=1; i<=m; i++)
        {
            if(edges[i].mark == 1)
            {
                edges[i].mark = -1;
                sum1 = 0;
                for(j=1; j<=n; j++)
                {
                    pre[j] = j;
                    rank[j] = 0;
                }
                count = 0;
                for(j=1; j<=m; j++)
                {
                    if(edges[j].mark != -1)
                        _union(edges[j], 2);
                }
                edges[i].mark = 0;
                if(count != n-1)
                    continue;
                if(sum1 == sum)
                {
                    printf("Not Unique!\n");
                    ok = 1;
                    break;
                }
            }
        }
        if(!ok)
        printf("%d\n", sum);
    }
    getch();
    return 0;
}