PDF《介绍 0》

while (BellmanFord(s, t, flow, cost));

return cost;

} }H;

char A[10000 + 10], B[5], C[10000 + 10], vis[2][52 + 10];

int mapp[26 + 10][26 + 10];

int main() { int tcase, n, m, k;

//freopen("in.txt", "r", stdin);

scanf("%d", &tcase);

while (tcase--) { scanf("%d%d%d", &n, &k, &m);

for (int i = 0;

i < n;

i++) { scanf("%s", B);

图论

79 First Chapter A[i] = B[0];

while (m--) { int s = 52, t = s+1;

H.init(t+1);

memset(mapp, 0, sizeof(mapp));

for (int i = 0;

i < n;

i++) { scanf("%s", B);

mapp[A[i] - 'A'][B[0] - 'A']++;

C[i] = B[0];

for (int i = 0;

i < 26;

i++) { for (int j = 0;

j < 26;

j++) { if (mapp[i][j]) { H.AddEdge(i, j+26, 1, -mapp[i][j]);

memset(vis, 0, sizeof(vis));

for (int i = 0;

i < n;

i++) { int a = A[i] - 'A', b = C[i]-'A'+26;

if (!vis[0][a]) { vis[0][a] = 1;

H.AddEdge(s, A[i] - 'A', 1, 0);

if (!vis[1][b]) { vis[1][b] = 1;

H.AddEdge(C[i]-'A'+26, t, 1, 0);

double len = n * 1.0;

printf("%.4f\n", -H.Mincost(s, t)*1.0/len);

} return 0;

} 图论

80 First Chapter 图论

81 First Chapter