poj 1861 Network(kruskal)

Memory: 356K

Time: 797MS

解题思路

题意：

    Andrew要在公司里用电缆连接n个集线器，要用总长度最小的线连接，求出其中最长的那根电缆。

    也就是告诉n个顶点，m条边，求最小生成树的最大边。并把生成树的每条边输出来，Sample里面的输出有问题，应该是三条。

 

思路：

   用并查集版的kruskal算法，把边按权值非递减排序，枚举每条边，如果它的两个顶点的根节点不是同一个，就合并，同时找出有最大的权的边，并把生成树的边的下标记录下来。最后输出最大权，和边的个数，还有那些边的顶点。花的时间很多，不知道该怎么优化了。本来想用sort替换qsort，不会用，搞半天一直WA。郁闷。

源程序

 

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

typedef struct
{
    int from, to;
    int cost;
}node;
node nodes[M];
int parent[N], rank[N];

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 ((node *)p)->cost > ((node *)q)->cost ? 1 : -1;
}


int main()
{
    int i, j;
    int n, m, a, b, count, max;
    int arr[N];

    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=0; i<m; i++)
    {
        scanf("%d%d%d", &nodes[i].from, &nodes[i].to, &nodes[i].cost);
        parent[nodes[i].from] = nodes[i].from;
        parent[nodes[i].to] = nodes[i].to;
    }
    max = 0;
    count = 0;
    qsort(nodes, m, sizeof(nodes[0]), cmp);

    for(i=0; i<m; i++)
    {
        a = find(nodes[i].from);
        b = find(nodes[i].to);
        if(a != b)
        {
            if(nodes[i].cost > max)
                max = nodes[i].cost;    //找出权最大的边
            count++;          //计数器记录有几条边
            arr[count] = i;   //记录要输出的边的下标
            _union(a, b);
        }
    }
    printf("%d\n%d\n", max, count);
    for(i=1; i<=count; i++)
        printf("%d %d\n", nodes[arr[i]].from, nodes[arr[i]].to);

    getch();
    return 0;
}