zoj1586 QS Network ——最小生成树入门题_Prim算法

May 3, 2013
zoj Graph

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=586 题目大意：　　题目意思比较难懂。看书上的翻译竟然没有看懂，还是打开OJ，看英文的原题。看了两遍的样子，终于差不多懂了。　　QS是一种生物，要完成通信，需要设备，每个QS需要的设备的价格不同，并且，这种设备只能在两个QS之间用一次，也就是说，如果一个QS需要和3个QS通信的话，它就必须得买3个设备，同时，对方三个也必须买对应的适合自己的设备。同时，每两个QS之间是有距离的，要完成通信还需要网线，给出每两个QS之间的网线的价值。求一棵生成树，使得所需要的费用最少。数据范围：所有数据都在1000以内。题目思路：　　根据这种设备的特性，每个设备只能和另外一个QS通信，所以呢，建图的时候，每条边的权值就是网线的费用，加上这条边的两个端点的QS所需设备的费用的和。这样，就转化成了常规的最小生成树的问题。因为只需要求出最小费用，所以，可以不必记录prim过程中要选的边的顶点编号，也就是说，可以省略nearvex数组，用lowcost数组就可以实现。如果lowcost[i]的值是-1，则代表已经选择了这个点，否则，lowcost[i]依然表示集合T1内的顶点 i 距离集合T内个顶点权值最小的边的权值。


#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;
int edge[MAX][MAX], lowcost[MAX];
int t, n, pri[MAX];
void prim(int u0) 
{
  int sum = 0, i, j, v;
  for (i = 1; i <= n; ++i) lowcost[i] = edge[u0][i];
  lowcost[u0] = -1;
  for (i = 1; i < n; ++i) {
    int min = MAXN; v = -1;
    for (j = 1; j <= n; ++j) {
      if (min > lowcost[j] && lowcost[j] != -1) {
        v = j; min = lowcost[j];
      }
    }
    if (v != -1) {
      sum += lowcost[v]; lowcost[v] = -1;
      for (j = 1; j <= n; ++j) {
        if (edge[v][j] < lowcost[j] && lowcost[j] != -1) {
          lowcost[j] = edge[v][j];
        }
      }
    }
  }
  printf("%d\n", sum);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj1568.in", "r", stdin);
#endif
  scanf("%d", &t);
  int i, j, k;
  while (t--) {
    memset(edge, 0, sizeof(edge));
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) scanf("%d", &pri[i]);
    for (i = 1; i <= n; ++i) {
      for (j = 1; j <= n; ++j) {
        scanf("%d", &edge[i][j]);
        edge[i][j] += (pri[i] + pri[j]);
      }
    }
    prim(1);
  }

  return 0;
}

写这道题目的时候，遇到一个比较坑的问题，导致输出怎么也不出结果。。。后来才发现，读文件那句话里的文件名写错了……好吧……我去……

Read more