2730750 2008-01-23 13:12:47 Accepted 1542 C++ 00:00.24 728K C.D. 求最大边最短的生成树。 我怀疑即为最小生成树【？】。因为假如按照Prim算法，每次求得的都为一个集合到另一个集合的最短边，也就是不可能生成两棵树，一颗三条边为2，2，2，一颗为1，1，3；这样的情况应该会产生1，1，2 的生成树。【未严格证明】 但是在求最大边的时候，显然是用排序+并查集更易得到结果。 值得注意的是几点。 1.在unionset操作里使用了不同的返回值分辨不同的处理情况。 2.qsort的处理。 /* zoj 1542 author: Crux.D date: 2008.1.23 description: mst, kruscal, n-1 edge*/ #include <cstdio>#include <string>#include <cstdlib> typedef struct{ int t1, t2, l;} Con; Con hub[15000], ans[1001];int N, M, ans_num, max_len; // hub个数，connection数量，生成树边数（N-1），最大边长度 int cmp ( const void *a, const void *b ){ Con *A = ( Con* ) a; Con *B = ( Con* ) b; if ( A->l == B->l ) { if ( A->t1 == B->t1 ) return A->t2 > B->t2; return A->t1 > B->t1; } return A->l > B->l;} void pt (){ int i; for ( i = 0; i < M; i ++ ) { printf ( "%d %d %d\n", hub[i].t1, hub[i].t2, hub[i].l ); }} int p[1001], num[1001]; void init_set (){ int i; for ( i = 0; i <= N; i ++ ) { p[i] = -1; num[i] = 1; } } int find_set ( int n ){ int pre = n; while ( p[pre] != -1 ) pre = p[pre]; int root = pre; while ( n != root ) { int t = p[n]; p[n] = root; n = t; } return root;} int union_set ( int n1, int n2 ){ int t1 = find_set ( n1 ); int t2 = find_set ( n2 ); if ( t1 == t2 ) return 0; if ( num[t1] < num[t2] ) { num[t2] += num[t1]; p[t1] = t2; } else { num[t1] += num[t2]; p[t2] = t1; } return 1;} void init (){ int i; for ( i = 0; i < M; i ++ ) { scanf ( "%d %d %d", &hub[i].t1, &hub[i].t2, &hub[i].l ); } qsort ( hub, M, sizeof ( hub[0] ), cmp ); init_set (); ans_num = 0; //pt ();} void build_mst (){ int i; int cur_cab = hub[0].l; for ( i = 0; i < M; i ++ ) { int v1 = hub[i].t1, v2 = hub[i].t2, len = hub[i].l; if ( union_set ( v1, v2 ) == 1 ) //表示可以归并，边加入后不会造成回路 { ans[ans_num].t1 = v1; ans[ans_num].t2 = v2; ans[ans_num ++].l = len; } if ( ans_num == N - 1 ) { max_len = len; break; } }} void print (){ printf ( "%d\n%d\n", max_len, ans_num ); int i; for ( i = 0; i < ans_num; i ++ ) { printf ( "%d %d\n", ans[i].t1, ans[i].t2 ); }} int main (){ //freopen ( "in.txt", "r", stdin ); while ( scanf ( "%d %d", &N, &M ) != EOF ) { init (); build_mst (); print (); } return 0;}
评论