# Out of Hay

### From Progteam

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); }