poj2421 Constructing Roads ——最小生成树入门题_Kruscal算法

May 2, 2013
POJ Graph

题目链接：http://poj.org/problem?id=2421 题目大意：　　给定一个矩阵，第 i 行第 j 列表示点 i 和点 j　的距离是ｓ［ｉ］［ｊ］。然后输入Ｑ，下面Ｑ行，每行两个数字ａ，ｂ表示点ａ和点ｂ已经有路相连。求需要至少再修多长的路，可以构成一棵生成树。输出需要在修的路的总长度。题目思路：　　转化为最小生成树求解。有两种思路：　　１）把已经相连的两个点的权值设置为０，这样，就可以直接求最小生成树了。因为kruscal的过程中，一定会选择到已经相连的这些点，因为它们的权值是0嘛，同时，即使把它们的权值加上，也不会影响结果。这个方法我好不容易想出来了，可是还有一个问题，就是：输入a b 后，如何定位到相应的边，并把这个边的权值设置为0？开始的时候，是暴力找，超时了，然后自己想各种方法，还求出来个公式，用a,b,N,表示出边的编号。最后还是超时了。。看网上别人恰好有人也是这么个思路，但是他是怎么定位边，并把边的权值设置为0的，没仔细看，不知道为什么人家就用这种方法过了…… 　　2）第二种思路，如果a b 已经相连，很简单，只要它俩的根节点不同，就把它两个合并不就可以了么，这样，kruscal的过程中，就不会再加入这些已经存在的边的权值了。剩下的就是纯的kruscal问题。这个方法很好！看的别人的想法。然后自己写了一下，RE了一次，原因是，合并a b 的时候，没有判断他们的根节点是否不同。。


#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}};
typedef struct Edge {
  int u, v, w;
  bool operator < (const Edge &o) const {
    return w < o.w;
  }
}Edge;
const int Mam = 5000+10, Man = 100+10;
Edge edge[Mam];
int parent[Man];
int N, Q, a, b, S[Man][Man], sum, ecnt;
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()
{
  int i, j, u, v, w, cnt = 0;
  for (i = 1; i < ecnt; ++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 (cnt >= N - 1) break;
  }
  printf("%d\n", sum);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2421.in", "r", stdin);
#endif
  int i, j, k, a, b;
  while (~scanf("%d", &N)) {
    sum = 0; k = 1;
    for (i = 1; i <= N; ++i) {
      for (j = 1; j <= N; ++j) {
        scanf("%d", &S[i][j]);
        if (i < j) {
          edge[k].u = i; edge[k].v = j;
          edge[k].w = S[i][j]; k++;
        }
      }
    }
    ecnt = k;
    init();
    scanf("%d", &Q);
    for (i = 0; i < Q; ++i) {
      scanf("%d%d", &a, &b);
      if (Find(a) != Find(b)) Union(a, b); //这里要判断一下根节点是不是相同，再合并！RE一次
    }
    sort(edge, edge + ecnt);
    kruscal();
  }

  return 0;
}

　　Code::Blocks超级难用赶脚……这两天老是用着用着就假死……然后强制关闭。。很不爽。。唉，还是回来乖乖地用gvim吧，自己学着写脚本，以后就不怕了。O(∩_∩)O哈哈~

Read more