poj1789 Truck History ——最小生成树入门题_Prim算法

May 3, 2013
POJ Graph

题目链接：http://poj.org/problem?id=1789 题目大意：　　输入一个数字n，然后输入n个长度为7的字符串，从任意一个字符串开始派生，直到派生出所有的字符串，两个字符串的距离规定为他们对应位置不相等的字母的个数，求出一种派生方案，使得派生方案的优劣值最大，并输出这个优劣值。优劣值的定义是：1/Σ(to,td)d(to,td) 表示对所有派生对的距离求和，再取倒数。题目了思路：　　要让优劣值最大，只需要距离之和最小，把7个字符串看成7个点，每两个点有一个距离，目的就是求权值最小的生成树，其实就是最小生成树。


#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 = 2000+10;
char a[MAX][MAX];
int edge[MAX][MAX];
int n, lowcost[MAX];
void prim(int u0) 
{
  int sum = 0, i, j, k;
  for (i = 1; i <= n; ++i) lowcost[i] = edge[u0][i];
  lowcost[u0] = -1;
  for (i = 1; i < n; ++i) {
    int v = -1, min = MAXN;
    for (j = 1; j <= n; ++j) {
      if (lowcost[j] != -1 && min > lowcost[j]) {
        min = lowcost[j]; v = j;
      }
    }
    if (v != -1) 
    {
      sum += lowcost[v]; lowcost[v] = -1;
      for (j = 1; j <=n; ++j) {
        if (edge[v][j] < lowcost[j]) {
          lowcost[j] =edge[v][j];
        }
      }
    }
  }
  printf("The highest possible quality is 1/%d.\n", sum);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj2158.in", "r", stdin);
#endif
  int i, j, k;
 while (~scanf("%d", &n) && n) {
    memset(edge, 0, sizeof(edge)); memset(lowcost, 0, sizeof(lowcost));
    for (i = 1; i <= n; ++i)
      scanf("%s", a[i]);
    int cnt;
    for (i = 1; i <= n; ++i) {
      for (j = i+1; j <= n; ++j) {
        cnt = 0;
        for (k = 0; k < 7; ++k) {
          if (a[i][k] != a[j][k]) cnt++;
        }
        edge[i][j] = edge[j][i] = cnt;
      }
    }
    prim(1);
  }

  return 0;
}

　　写的过程中，依然是WA了好多次，样例是过了，但是程序就是不知道哪里错了。后来自己出了组数据，才发现了错误，原来prim过程里面的一个 lowcost[j] 写成了 lowcost[v]……唉，程序本身原来就是错的。又是这种细节，，这些中间变量最容易错了。从现在开始，要特别小心。敲代码一定要认真。老是出这种错误，也许这就是为什么我效率这么低的原因。。唉…… 　　另外就是，程序出错了之后，自己耐心地出有效的数据也是一种能力。

Read more