poj 1258 Agri-Net

Memory: 256K

Time: 47MS

解题思路

题意：

    John要用最少的光纤去连接所有的农场。最小生成树问题。

思路：

    Prim算法和kruskal算法都可以用，prim更简单也更合适，但是为了复习，就用了后者。把各条边放在一个数组里，非递减排序，从小到大一次看他们的顶点是不是在同一个集合中，不是的话把权加起来，并合并。寻找祖先节点的时候要用到并查集里面的压缩路径，合并的时候把高度小的树的祖先指向高度大的祖先也可以优化。由于没搞清楚无向图的边的个数和顶点的个数的关系，RE了好几次。

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 110
#define M N*(N-1)/2

typedef struct
{
    int from;
    int to;
    int weight;
}edge;

edge e[M];
int parent[M];
int rank[M];

int find(int x)
{
    int y, z;

    y = x;
    while(parent[y] != y)
        y = parent[y];
    while(x != y)
    {
        z = parent[x];
        parent[x] = y;
        x = z;
    }
    return y;
}

void _union(int x, int y)
{
    if(rank[x] > rank [y])
    {
        parent[y] = x;
    }
    else
    {
        if(rank[x] == rank[y])
            rank[y]++;
        parent[x] = y;
    }
}

int cmp(const void *p, const void *q)
{
    return ((edge *)p)->weight > ((edge *)q)->weight ? 1 : -1;
}

int main()
{
    int i, j, x, a, k, y;
    int n, sum;
    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
    {
        k = 0;
        memset(e, 0, sizeof(e));
        memset(rank, 0, sizeof(rank));
        memset(parent, 0, sizeof(parent));
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
            {
                if(j <= i)
                    scanf("%d", &a);
                else
                {
                    scanf("%d", &e[k].weight);
                    e[k].from = i+1;
                    e[k].to = j+1;
                    parent[k] = k;
                    k++;
                }
            }
        qsort(e, k, sizeof(e[0]), cmp);
        sum = 0;
        for(i=0; i<k; i++)
        {
            x = find(e[i].from);
            y = find(e[i].to);
            if(x != y)
            {
                printf("%d %d\n", e[i].from, e[i].to);
                sum += e[i].weight;
                _union(x, y);
            }
        }
        printf("%d\n", sum);
    }
    getch();
    return 0;
}