zoj1203 Swordfish ——最小生成树入门题_Kruscal算法

May 1, 2013
zoj Graph

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=203 题目大意：　　给定N个点的坐标，求经过这N个点的路线长度总和的最小值。题目思路：　　求出任意两点之间的距离，然后就是最小生成树。　　写的过程中还是遇到了三个问题，有一个局部变量没有初始化；没有把边按照权值排序；另外就是没有看输出，每两个case之间有一个空行。这里有一个十分常见的问题，就是最后一个case后面没有空行。否则会PE。


#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; double w;
  bool operator < (const Edge &other) const {
    return w < other.w;
  }
}Edge;
Edge edge[5000];
int parent[109];
int N, m;
double X[109], Y[109], sum;
void init() {
  int i;
  for (i = 0; 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);
  int 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 num = 0, u, v, i;
  init();
  for (i = 0; i < m; ++i) {
    u = edge[i].u; v = edge[i].v;
    if (find(u) != find(v)) {
      sum += edge[i].w; num++;
      Union(u, v);
    }
    if (num >= N - 1) break;
  }
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj1203.in", "r", stdin);
#endif
  int c = 1;
  while (1) {
    scanf("%d", &N);
    if (!N) break;
    if (c != 1) printf("\n");
    printf("Case #%d:\nThe minimal distance is: ", c);c++;
    int i, j;
    for (i = 0; i < N; ++i) {
      scanf("%lf%lf", &X[i], &Y[i]);
    }
    int cnt = 0; double dis;
    for (i = 0; i < N; ++i) {
      for (j = i + 1; j < N; ++j) {
        dis = sqrt( (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]) );
        edge[cnt].u = i; edge[cnt].v = j; edge[cnt].w = dis; cnt++;
      }
    }
    m = cnt; sum = 0.0;
    sort(edge, edge + m);
    kruscal(); printf("%.2f\n", sum);
  }

  return 0;
}

　　写代码最重要的一点还是要认真，变量初始化神马的，大于号小于号神马的，一些关键步骤不要漏掉，这些东西都要注意。细心一点。

Read more