poj2349 Arctic Network ——最小生成树入门题_Prim算法

May 3, 2013
POJ Graph

题目链接：http://poj.org/problem?id=2349 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=914 题目大意：　　有一些炮台，如果这个炮台有卫星接收器，那么任意两个有卫星接收器的炮台可以通信，不受距离限制；否者，两个炮台之间只能通过对讲机通信，这是受距离限制的。要买一种对讲机，用在需要的炮台上，要求所有炮台两两之间可以直接或者间接通信，问要买通信距离至少为多少的对讲机可以满足要求。输入：S卫星接收器的数量，P炮台的数量，然后是P行，每行代表一个炮台的坐标。输出要求的对讲机的通信距离D。题目思路：　　题目意思比较难懂。关键是satellite channel的安放方法，注意，它是放在炮台上的，只要这个炮台上有这货，它就可以和任何也有这货的炮台通信。明白这一点，然后就简单了。有S个卫星接收器，那么就可以减少S-1个距离开销。要让D尽可能小，就让这S-1个距离开销最大，所以，想法就是，求这些点的最小生成树，然后把所选的边排序，第S大的边的权值就是所求。　　开始题意没搞懂。关键是“Any two outposts with a satellite channel can communicate via the satellite, regardless of their location.”这句话没有理解明白，也就是说，任何两个有卫星接收器的炮台都可通信！然后自己就把问题复杂化了……写的代码就很复杂了。。后来改了一下，就过了。。


#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  = 500+10;
int n, s, p;
double edge[MAX][MAX];
double lowcost[MAX];
int nearvex[MAX];

typedef struct Point {
  double x, y;
}Point;

typedef struct Vex {
  int i, j; double len;
  bool operator < (const Vex & other) const { // 不能写反了
    return len > other.len;
  }
}Vex;

map<int, bool> visit;
Vex vex[MAX];
Point point[MAX];

void prim(int u0) {
  int v;  // 尼玛定义类型错了，我去……
  int cur = 0, i, j;
  visit.clear();
  for (i = 1; i <= p; ++i) {
    lowcost[i] = edge[u0][i]; nearvex[i] = u0;
  }
  lowcost[u0] = 0; nearvex[u0] = -1;
  for (i = 1; i < p; ++i) {
    v = -1; double min = MAXN*1.0;
    for (j = 1; j <= p; ++j) {
      if (lowcost[j] < min && nearvex[j] != -1) {
        min = lowcost[j]; v = j;
      }
    }
    if (v != -1) {
      nearvex[v] = -1;
      vex[cur].i = v; vex[cur].j = nearvex[v]; vex[cur].len = lowcost[v];
      cur++;
      for (j = 1; j <= p; ++j) {
        if (lowcost[j] > edge[v][j] && nearvex[j] != -1) {
          lowcost[j] = edge[v][j]; nearvex[j] = v;
        }
      }
    }
  }
  sort(vex, vex + cur); 
  printf("%.2f\n", vex[s-1].len); 
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2349.in", "r", stdin);
#endif
  scanf("%d", &n);
  int i, j;// k;
  while (n--) {
    scanf("%d%d", &s, &p);
    for (i = 1; i <= p; ++i) {
      scanf("%lf%lf", &point[i].x, &point[i].y);
    }
    for (i = 1; i <= p; ++i) {
      for (j = i + 1; j <= p; ++j) {
        double x1=point[i].x,y1 =point[i].y,x2 = point[j].x, y2=point[j].y;
        double dis = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        edge[i][j] = edge[j][i] = dis;
      }
    }
    prim(1);
  }

  return 0;
}

　　唉，好复杂的代码……题意理解最重要了，这种题目应该考的就是题意…… 　　还有就是，结构体里面重载运算符的时候，貌似不能重载大于号？因为要逆序排序么，然后就把return改了一下。

Read more