poj1861&&zoj1542 Network ——最小生成树入门题_Kruscal算法

May 1, 2013
POJ Graph

题目链接：http://poj.org/problem?id=1861 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=542 题目大意：　　给n个点，m条边。求一棵生成树，并且满足任意两点之间的距离的最大值最小。输出这个最大值，然后输出树的边的数量，最后输出树的每条边。题目思路：　　其实就是求最小生成树。关键就是证明，对于一个图的最小生成树来说，它的最大边满足在所有的生成树的最大边里最小。这是可以理解的。简单思考一下：假设最小生成树不满足这个条件。那么就是说，存在另一棵生成树，它的最大边的值比最小生成树还小，但是它的权值之和可能比最小生成树大，但是这表明，构造最小生成树的时候，存在一步，选择边的时候，没有选择权值最小的，这是不可能的。所以矛盾。所以假设不成立。所以，问题就转化成了常规的求最小生成树的问题了。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 1000+10;
const int MAX1 = 15000+10;
typedef struct Edge {
  int u, v, w;
  bool operator < (const Edge &other) const {
    return w < other.w;
  }
};
struct re {
  int u, v;
}Re[MAX];
Edge edge[MAX1];
int parent[MAX];
int n, m, sum;
void init()
{
  for (int i = 1; i <= n; ++i) parent[i] = -1;
}
int Find(int x)
{
  int s;
  for (s = x; parent[s] >= 0; s = parent[s]) ;
  while (s != x) {
    int tmp = parent[x]; parent[x] = s; x = tmp;
  }
  return s;
}
void Union(int R1, int R2)
{
  int r1 = Find(R1), r2 = Find(R2), tmp = parent[r1] + parent[r2];
  if (parent[r1] > parent[r2]) {
    parent[r1] = r2; parent[r2] = tmp;
  } else {
    parent[r2] = r1; parent[r1] = tmp;
  }
}
void kruscal()
{
  init();
  int i, j = 0, u, v, w, cnt = 0, Max = 0;
  for (i = 0; i < m; ++i) {
      u = edge[i].u; v = edge[i].v; w = edge[i].w;
    if (Find(u) != Find(v)) {
      sum += w; Union(u, v); cnt++;
      if (w > Max) Max = w;
      Re[j].u = u; Re[j].v = v; j++;
    }
    if (cnt >= n - 1) break;
  }
  cout << Max << endl << n - 1 << endl;
  for (i = 0; i < j; ++i) {
    printf("%d %d\n", Re[i].u, Re[i].v);
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1861.in", "r", stdin);
#endif
  int i, j;
  while (~scanf("%d%d", &n, &m)) {
    sum = 0; int u, v, w;
    for (i = 0; i < m; ++i) {
      scanf("%d%d%d", &u, &v, &w);
      edge[i].u = u; edge[i].v = v; edge[i].w = w;
    }
    sort(edge, edge + m);
    kruscal();
  }

  return 0;
}

这题应该属于简单题，但是还是卡了一下。原因很悲催，输入里面的格式控制符多打了一个“%”，我去……结果怎么也出不来啊，直接输出输入的数字也数不出来！竟然很长时间都没有发现，后来还是把输入的部分重新打了一遍，才发现问题。唉，最近老是打错…… 还有就是，题目里面的样例输出是错的……好吧，，第一次遇到这种情况。。还好看的是书里面的翻译和解释，要不又得把题目一遍一遍地读……

Read more