|
|
這題絕對不是蓋的。 題目大意是： 給出一個無向圖，和四對數據。每對數據分別為圖中的兩個點。 要求添加一些邊，使每對點都能連通，讓總邊權最小。 首先考慮一個子問題：指定一些點，添加一些邊，讓它們連通，并且總邊權最小。 這個問題就是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;
}
|