poj2048&&zoj1751 Highways ——最小生成树入门题_Prim算法

May 4, 2013
POJ Graph

题目链接：http://poj.org/problem?id=1751 　　http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1048 题目大意：　　给定n个点的坐标。还有m对已经相连的点的编号。求连接这n个点的总权值最小的一棵生成树，输出还需要连接的点的编号。题目思路：　　这道题目和以前做过的poj2421是一样的。这里采用了那篇博客里面的第一种方法。幸运的是，在poj上1A了。但是在zoj上，因为输入输出格式有一些不一样，卡了一下，到最后我也没明白“If no new highways need to be built (all towns are already connected), then the output should be created but it should be empty.” 这句话的含义，看书上的翻译是，如果不需要再建了，输出一个空行。可是，在poj上，输出空行与否都是可以过的。在zoj上，输出空行就WA了，就是因为这个错误…… poj代码：


#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 = 759;
double edge[MAX][MAX];
double lowcost[MAX];int nearvex[MAX];
int n, m;
typedef struct Point {
  int x, y;
}Point;
Point point[MAX];
void prim(int u0) {
  int i, j, k, v;double sum = 0;
  for (i = 1; i <= n; ++i) {
    lowcost[i] = edge[i][u0]; nearvex[i] = u0;
  }
  lowcost[u0] = 0; nearvex[u0] = -1;
  for (i = 1; i < n; ++i) {
    double min = 1.0*MAXN;int v = -1;
    for (j = 1; j <= n; ++j) {
      if (nearvex[j] != -1 && lowcost[j] < min) {
        min = lowcost[j]; v = j;
      }
    }
    if (v != -1){
      if (lowcost[v] != 0) {
        printf("%d %d\n", v, nearvex[v]);
      }
      sum += lowcost[v]; nearvex[v] = -1;
      for (j = 1; j <= n; ++j) {
        if (nearvex[j] != -1 && edge[v][j] < lowcost[j]) {
          lowcost[j] = edge[v][j]; nearvex[j] = v;
        }
      }
    }
  }
  if (sum == 0) printf("\n\n");
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1751.in", "r", stdin);
#endif
  while (~scanf("%d", &n)) {
    int i, j, k;
    for (i = 1; i <= n; ++i) {
      scanf("%d%d", &point[i].x, &point[i].y);
    }
    for (i = 1; i <= n; ++i) {
      for (j = i+1; j <= n; ++j) {
        int x1, y1; x1 = point[i].x-point[j].x;
        y1 = point[i].y-point[j].y;
        edge[j][i]=edge[i][j] = sqrt(pow(x1,2.0)+pow(y1,2.0));
      }
    }
    scanf("%d", &m);
    int a, b;
    for (i = 1; i <= m; ++i) {
      scanf("%d%d", &a, &b);
      edge[a][b] = edge[b][a] = 0;
    }
    prim(1);
  }

  return 0;
}

zoj代码：


#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 = 759;
double edge[MAX][MAX];
double lowcost[MAX];int nearvex[MAX];
int n, m;
typedef struct Point {
  int x, y;
}Point;
Point point[MAX];
void prim(int u0) {
  int i, j, k, v;double sum = 0;
  for (i = 1; i <= n; ++i) {
    lowcost[i] = edge[i][u0]; nearvex[i] = u0;
  }
  lowcost[u0] = 0; nearvex[u0] = -1;
  for (i = 1; i < n; ++i) {
    double min = 1.0*MAXN;int v = -1;
    for (j = 1; j <= n; ++j) {
      if (nearvex[j] != -1 && lowcost[j] < min) {
        min = lowcost[j]; v = j;
      }
    }
      if (lowcost[v] != 0) {
        printf("%d %d\n", v, nearvex[v]);
      }
      sum += lowcost[v]; nearvex[v] = -1;
      for (j = 1; j <= n; ++j) {
        if (nearvex[j] != -1 && edge[v][j] < lowcost[j]) {
          lowcost[j] = edge[v][j]; nearvex[j] = v;
        }
      }
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1751.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    int i, j, k;
    for (i = 1; i <= n; ++i) {
      scanf("%d%d", &point[i].x, &point[i].y);
    }
    for (i = 1; i <= n; ++i) {
      for (j = i+1; j <= n; ++j) {
        int x1, y1; x1 = point[i].x-point[j].x;
        y1 = point[i].y-point[j].y;
        edge[j][i]=edge[i][j] = (pow(x1,2.0)+pow(y1,2.0));
      }
    }
    scanf("%d", &m);
    int a, b;
    for (i = 1; i <= m; ++i) {
      scanf("%d%d", &a, &b);
      edge[a][b] = edge[b][a] = 0;
    }
    prim(1);
    if (t!=0) printf("\n");
  }

  return 0;
}

　　另外，还有一个小trick，因为不需要求最后的权值，我求的距离的作用是标记一下是不是到最后都不需要再建了，来决定是不是需要输出空行，虽然现在赶脚这个很多余……o(╯□╰)o 所以呢，注意到坐标范围是在10000以内，所以可以省掉sqrt()也不会溢出，就省去了开方的运算，直接用平方和表征距离，这样不就可以节省点儿时间了么……O(∩_∩)O哈哈~

Read more