https://cn.vjudge.net/problem/POJ-3123

题意：

n 个城市，m 条路，给定八个点（也就是四对），使每队点连通且总权和最小。

分析：

dp[i][j] 表示 i 状态下以 j 为起点的最小总权和。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <map>
typedef long long int ll;
const int MOD = (int)1e9 + 7;
const int INF = 99999999;
using namespace std;int n, m;
map<string, int> city;
int dp1[1 << 8][35];
int dp2[1 << 8];
int d[35][35];
int vis[35];bool check(int s)
{for (int i = 0; i < 4; i++){if (((s & 3) != 3) && ((s & 3) != 0))return false;s >>= 2;}return true;
}int main()
{while (~scanf("%d%d", &n, &m) && (n || m)){for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)d[i][j] = (i == j) ? 0 : INF;string s1, s2;int w;for (int i = 0; i < n; i++){cin >> s1;city[s1] = i;}for (int i = 0; i < m; i++){cin >> s1 >> s2 >> w;int u = city[s1];int v = city[s2];if (w < d[u][v])d[u][v] = d[v][u] = w;}// Floydfor (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);for (int i = 0; i < 8; i++){cin >> s1;for (int j = 0; j < n; j++)dp1[1 << i][j] = d[j][city[s1]];}for (int i = 0; i < (1 << 8); i++){if (!(i & (i - 1)))continue;for (int j = 0; j < n; j++){dp1[i][j] = INF;for (int sub = (i - 1) & i; sub != 0; sub = (sub - 1) & i)dp1[i][j] = min(dp1[i][j], dp1[sub][j] + dp1[i - sub][j]);}memset(vis, 0, sizeof(vis));int min_w, min_i;for (int j = 0; j < n; j++){min_w = INF;for (int k = 0; k < n; k++){if (dp1[i][k] < min_w && !vis[k]){min_w = dp1[i][k];min_i = k;}}vis[min_i] = 1;for (int k = 0; k < n; k++)dp1[i][min_i] = min(dp1[i][min_i], dp1[i][k] + d[k][min_i]);}}for (int i = 0; i < (1 << 8); i++){dp2[i] = INF;for (int j = 0; j < n; j++)dp2[i] = min(dp2[i], dp1[i][j]);}for (int i = 0; i < (1 << 8); i++){if (check(i)){for (int j = i; j != 0; j = (j - 1) & i){if (check(j))dp2[i] = min(dp2[i], dp2[j] + dp2[i - j]);}}}printf("%d\n", dp2[(1 << 8) - 1]);}return 0;
}