Out of Hay

From Progteam

Revision as of 03:42, 7 March 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.



Out of Hay
Problem Number 2395
Sorter: mlc413
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2395



Out of Hay is problem number 2395 on the Peking University ACM site.

Minimum Spanning Tree problem.

Here's my code. The basic strategy is to sort the input by weight, since you are looking for the spanning tree that minimizes the weight of the heaviest edge. Then set the initial weight to the lightest edge from node 1, since you must begin at node 1. Mark every pair that is lighter than the lightest node 1 edge as connected. then go through the list in order, checking both ends of the edge to see if it is connected yet or not. If it is not, update the heaviest weight and mark as connected. Since we are told that there is a path from the first node to all other nodes we need not worry about how they are connected. Time should be limited by the quicksort.

It gives the correct answer on all the input I've given it, including maximum input and the sample. It gives Wrong Answer on PKU. Help much appreciated, even if it is just a suggestion for crazy input. -Kerry
Heh, you like problems with numbers in the trillions in the description, don't you? -Hjfreyer

Thanks to some doodling and a hint from Hunter, I've got it now, smokin' fast and no memory usage! -Kerry

#include <stdio.h>
#include <stdlib.h>

typedef struct Edge {
        long weight;
        int left;
        int right;
} edge;

int getinput(edge *, int);
long get_longest(edge *, char *, long, int, int);
int compare(const void *, const void *);

int main() {
edge *edges;
int num_v, i, num_edges, index;
long longest=0, answer;
char * connected;

                scanf("%d %ld", &num_v, &num_edges);
                edges = (edge *)malloc(sizeof(edge)*num_edges);
                connected = (char *)malloc(sizeof(char)*num_v);
                for (i=0;i<num_v;i++)
                        connected[i]=0;
                getinput(edges, num_edges);
                qsort(edges, num_edges, sizeof(edge), compare);
                answer = get_longest(edges, connected, longest, num_edges, num_v);
                printf("%ld\n", answer);
}

long get_longest(edge *edges, char *connected, long longest, int num_edges, int num_v) {
int i,j,index, *id, *size;

        index=0;
        id=(int *)malloc(sizeof(int)*num_v);
        size=(int *)malloc(sizeof(int)*num_v);

        for(i=0;i<=num_v;i++) {
                id[i]=i;
                size[i]=1;
        }
        while(index<num_edges) {
                for(i=(edges+index)->left;i!=id[i];i=id[i]);
                for(j=(edges+index)->right;j!=id[j];j=id[j]);
                if(i==j) {
                        index++;
                        continue;
                }
                else
                        if (size[i]<size[j]) {
                                longest = (edges+index)->weight;
                                id[i]=j;
                                size[j]+=size[i];
                        }
                        else {
                                longest = (edges+index)->weight;
                                id[j]=i;
                                size[i]+=size[j];
                        }

                index++;
        }
        return longest;
}

int getinput(edge *edges, int num_edges) {
int i, l, r;
long weight;

        for(i=0;i<num_edges;i++) {
                scanf("%d %d %ld", &l, &r, &weight);
                (edges+i)->weight=weight;
                (edges+i)->left=l;
                (edges+i)->right=r;
        }
        return 0;
}

int compare(const void *a, const void *b) {
        return (((edge *)a)->weight-((edge *)b)->weight);
}

Personal tools