wordpress站点地址修改,网站建设学习课程,世界青田网app,长安镇做网站题目链接#xff1a;http://poj.org/problem?id1789 题目的大概意思就是给你n个字符串。每个字符串只有7的长度。然后分别给这些字符串编号。不同编号之间的距离就是他们有多少个不同的字母。#xff08;同一个位置字母不相同也算#xff09;然后一个编号只能由另一个派生… 题目链接http://poj.org/problem?id1789 题目的大概意思就是给你n个字符串。每个字符串只有7的长度。然后分别给这些字符串编号。不同编号之间的距离就是他们有多少个不同的字母。同一个位置字母不相同也算然后一个编号只能由另一个派生出来。派生的代价就是他们呢之间的距离。现在要你求最小的总代价。 编号的范围是2-2000.属于稠密图。求最小生成树最好用prim算法。用克鲁斯卡尔会可能会超时。 #includestdio.h
#includestring.h
#includeiostream
#includealgorithm
using namespace std;
const int N2220;
int G[N][N];
int low[N],vis[N];
char s[N][10];
int n;
int prim()
{memset(vis,0,sizeof(vis));int pos0;int min;int ans0;vis[0]1;for(int i0;in;i)low[i]G[pos][i];for(int i0;in-1;i){min100;for(int j0;jn;j){if(!vis[j]low[j]min){minlow[j];posj;}}vis[pos]1;ansmin;for(int j0;jn;j){if(!vis[j]low[j]G[pos][j])low[j]G[pos][j];}}return ans;
}
int main()
{while(scanf(%d,n)!EOFn){for(int i0;in;i)scanf(%s,s[i]);int cnt0;for(int i0;in;i){for(int ji1;jn;j){int tmp0;for(int k0;k7;k){if(s[i][k]!s[j][k])tmp;}int ui;int vj;G[u][v]tmp;G[v][u]tmp;}}int ansprim();printf(The highest possible quality is 1/%d.\n,ans); }return 0;
} 转载于:https://www.cnblogs.com/NaCl/p/9580120.html
