首页 > 代码库 > poj 1789 Truck History 解题报告

poj 1789 Truck History 解题报告

2024-07-17 20:48:16   225人阅读

题目链接：http://poj.org/problem?id=1789

题目意思：给出 N 行，每行7个字符你，统计所有的 行 与 行 之间的差值（就是相同位置下字母不相同），一个位置不相同就为1，依次累加。问最终的差值最少是多少。

      额.....题意我是没看懂啦= =......看懂之后，就转化为最小生成树来做了。这是一个完全图，即每条边与除它之外的所有边都连通。边与边的权值是通过这个差值来算出来的。

     

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 const int maxn = 2000 + 10; 6 const int INF = 1e9; 7 int truck[maxn][maxn]; 8 int dist[maxn], vis[maxn]; 9 char input[maxn][maxn];10 int ans, N;11 12 void prim()13 {14     int k;15     for (int i = 1; i <= N; i++)16     {17         vis[i] = 0;18         dist[i] = INF;19     }20     dist[1] = 0;21     for (int i = 1; i <= N; i++)22     {23         int tmp = INF;24         for (int j = 1; j <= N; j++)25         {26             if (!vis[j] && dist[j] < tmp)27             {28                 tmp = dist[j];29                 k = j;30             }31         }32         vis[k] = 1;33         ans += tmp;34         for (int j = 1; j <= N; j++)35         {36             if (!vis[j] && dist[j] > truck[k][j])37                 dist[j] = truck[k][j];38         }39     }40 }41 42 int main()43 {44     while (scanf("%d", &N) != EOF && N)45     {46         for (int i = 1; i <= N; i++)47             scanf("%s", &input[i]);48         int cnt;49         for (int i = 1; i < N; i++)50         {51             for (int j = i+1; j <= N; j++)52             {53                 cnt = 0;54                 for (int k = 0; k < 7; k++)55                 {56                     if (input[i][k] != input[j][k])57                         cnt++;58                 }59                 truck[i][j] = truck[j][i] = cnt;60             }61         }62         ans = 0;63         prim();64         printf("The highest possible quality is 1/%d.\n", ans);65     }66     return 0;67 }

 


联系
我们