求最大边最短的生成树。

我怀疑即为最小生成树【？】。因为假如按照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;
}
  

评论