poj1789
仍然prim,改都不用改。边权是,字符串之间变化的字符的个数。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
#pragma optimize( "/Ox", on )
#pragma warning(disable:4996)
#define maxn 2005
#define typec int
#define inf 0x3f3f3f3f
int map[maxn][maxn];
int vis[maxn]; typec lowc[maxn];
string s[maxn];
typec prim(typec cost[][maxn],int n)
{
int i, j, p;
typec minc, res = 0;
memset(vis, 0, sizeof(vis));
vis[0] = 1;
for (i = 1; i < n; i++) lowc[i] = cost[0][i];
for (i = 1; i < n; i++)
{
minc = inf; p = -1;
for (j = 0; j<n; j++)
if (0 == vis[j] && minc > lowc[j])
{
minc = lowc[j]; p = j;
}
//if (res < minc) res = minc;
//vis[p] = 1;
if (inf == minc) return -1;
res += minc; vis[p] = 1;
for (j = 0; j<n; j++)
if (0 == vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
return res;
}
int diff(int a, int b, string *s)
{
int countt = 0;
for (int i = 0; i < 7; i++)
if (s[a][i] != s[b][i])
countt++;
return countt;
}
int main()
{
ios::sync_with_stdio(false);
int t;
while(cin >> t && t)
{
for (int i = 0; i < t; i++) cin >> s[i];
for (int i = 0; i < t; i++)
{
for (int j = 0; j < t; j++)
{
map[i][j] = diff(i, j, s);
}
}
cout << "The highest possible quality is 1/" << prim(map, t) << '.' << endl;
}
return 0;
}
补充:软件开发 , C++ ,