|
|
这题绝对不是盖的。 题目大意是： 给出一个无向图，和四对数据。每对数据分别为图中的两个点。 要求添加一些边，使每对点都能连通，让总边权最小。 首先考虑一个子问题：指定一些点，添加一些边，让它们连通，并且总边权最小。 这个问题就是Minimal Steiner Tree问题，解决方法可以见 这里。 这问题不是盖的，它居然是NP完全问题。。 汗。。今天终于在POJ见识到啥叫NP完全问题了。。 大的问题可以分为多个子问题。可以枚举所有pair的连接状况。 比如说 {1和2链接，3和4链接} 或者 {1独立，2独立，3和4链接} 等等 一共有15种情况。分别为 // 1,1,1,1 {{1},{2},{3},{4}}, // 1,1,2 {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}, {{2,3},{1},{4}}, {{2,4},{1},{3}}, {{3,4},{1},{2}}, // 2,2 {{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}}, // 1,3 {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, // 4 {{1,2,3,4}}, 其中有一些是重复的，就可以开一个数组保存下来。 贴一个我的程序。当然，这个是TLE的。。官方的数据需要将近一分钟才能跑完。 另外一个标程运行飞快，用得是更好的方法，点 这里。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
char names[32][32];
int N, M;
int W[32][32];
const int INF = 10032*32;
int pairs[4];
int dp[256][2], dn;
int getcity(char *s)
{
int i;
for (i = 0; i < N; i++)
if (!strcmp(s, names[i]))
break;
return i;
}
int prim(int mask)
{
int i, j, mc, mi, a, c, t;
c = 0;
for (i = 0; i < N; i++)
if (mask & (1 << i)) {
a = 1 << i;
c++;
}
t = 0;
while (--c) {
mc = INF;
for (i = 0; i < N; i++)
if (a & (1 << i))
for (j = 0; j < N; j++)
if (((mask ^ a) & (1 << j)) && W[i][j] < mc) {
mc = W[i][j];
mi = j;
}
if (mc == INF)
return INF;
a |= 1 << mi;
t += mc;
}
return t;
}
int K;
int dfs(int start, int mask, int n)
{
int i, r;
if (n >= K - 2)
return prim(mask);
r = prim(mask);
for (i = start; i < N; i++)
if ((1 << i) & ~mask)
r = min(r, dfs(i+1, mask|(1<<i), n+1));
return r;
}
int minicost(int mask)
{
int i, r;
for (i = 0; i < dn; i++)
if (mask == dp[i][0])
return dp[i][1];
K = 0;
for (i = 0; i < N; i++)
if (mask & (1 << i))
K++;
r = dfs(0, mask, 0);
dp[dn][0] = mask;
dp[dn][1] = r;
dn++;
return r;
}
int stats[15][8][8] = {
// 1,1,1,1
{{1},{2},{3},{4}},
// 1,1,2
{{1,2},{3},{4}},
{{1,3},{2},{4}},
{{1,4},{2},{3}},
{{2,3},{1},{4}},
{{2,4},{1},{3}},
{{3,4},{1},{2}},
// 2,2
{{1,2},{3,4}},
{{1,3},{2,4}},
{{1,4},{2,3}},
// 1,3
{{1,2,3},{4}},
{{1,2,4},{3}},
{{1,3,4},{2}},
{{2,3,4},{1}},
// 4
{{1,2,3,4}},
};
int main()
{
int i, j, k, a, b, c, ans;
char sa[32], sb[32];
while (scanf("%d%d", &N, &M), N) {
for (i = 0; i < N; i++)
scanf("%s", names[i]);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
W[i][j] = INF;
for (i = 0; i < M; i++) {
scanf("%s%s%d", sa, sb, &c);
a = getcity(sa);
b = getcity(sb);
W[a][b] = W[b][a] = min(W[a][b], c);
}
for (i = 0; i < 4; i++) {
scanf("%s%s", sa, sb);
a = getcity(sa);
b = getcity(sb);
pairs[i] = (1 << a) | (1 << b);
}
// floyd
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
W[i][j] = min(W[i][k] + W[k][j], W[i][j]);
dn = 0;
ans = INF;
for (i = 0; i < 15; i++) {
c = 0;
for (j = 0; stats[i][j][0]; j++) {
a = 0;
for (k = 0; stats[i][j][k]; k++)
a |= pairs[stats[i][j][k] - 1];
c += minicost(a);
}
ans = min(ans, c);
}
printf("%d\n", ans);
}
return 0;
}
|