学步园

所谓最小斯泰纳树，很裸，直接套版

/*<br /> * File: HNU 10862 Ticket to Ride<br /> * Author: xiaotian @ hnu<br /> * Created on 2010年10月6日, 下午7:48<br /> * 题解：最小斯泰纳树，直接套板<br /> */<br /> #include<stdio.h><br /> #include<iostream><br /> #include<string><br /> #include<queue><br /> #include<map><br /> #include<set><br /> #include<math.h><br /> using namespace std;<br /> #define N 1000<br /> #define A 8<br /> #define inf 0x7ffffff<br /> int vis[N], id[A]; //id[]: A中点的标号<br /> int d[N][N], dp[1 << A][N]; //dp[i][v]: 点v到点集i的最短距离<br /> map<string, int>mp, fg;<br /> int min(int a, int b) {<br /> return a < b ? a : b;<br /> }<br /> void steiner(int n, int a) {<br /> int i, j, k, mx, mk, top = (1 << a);<br /> for (k = 0; k < n; k++)<br /> for (i = 0; i < n; i++)<br /> for (j = 0; j < n; j++)<br /> if (d[i][j] > d[i][k] + d[k][j])<br /> d[i][j] = d[i][k] + d[k][j];<br /> for (i = 0; i < a; i++) { // vertex: 0 ~ n-1<br /> for (j = 0; j < n; j++)<br /> dp[1 << i][j] = d[j][ id[i] ];<br /> }<br /> for (i = 1; i < top; i++) {<br /> if (0 == (i & (i - 1))) continue;<br /> memset(vis, 0, sizeof (vis));<br /> for (k = 0; k < n; k++) { // init<br /> for (dp[i][k] = inf, j = 1; j < i; j++)<br /> if ((i | j) == i &&<br /> dp[i][k] > dp[j][k] + dp[i - j][k])<br /> dp[i][k] = dp[j][k] + dp[i - j][k];<br /> }<br /> for (j = 0; mx = inf, j < n; j++) { // update<br /> for (k = 0; k < n; k++)<br /> if (dp[i][k] <= mx && 0 == vis[k])<br /> mx = dp[i][mk = k];<br /> for (k = 0, vis[mk] = 1; k < n; k++)<br /> if (dp[i][mk] > dp[i][k] + d[k][mk])<br /> dp[i][mk] = dp[i][k] + d[k][mk];<br /> }<br /> }<br /> }<br /> int main() {<br /> int n, m, a = 8, w;<br /> char s1[25], s2[25];<br /> while (scanf("%d%d/n", &n, &m) != EOF) {<br /> if (n == 0 && m == 0) return 0;<br /> mp.clear();<br /> for (int i = 0; i < n; i++) {<br /> scanf("%s",s1);<br /> mp[s1] = i + 1;<br /> }<br /> for (int i = 0; i <= n; i++)<br /> for (int j = 0; j <= n; j++) d[i][j] = i==j?0:inf;<br /> for (int i = 0; i < m; i++) {<br /> scanf("%s %s %d", s1, s2, &w);<br /> //printf("%s %s %d/n",s1,s2,w);<br /> int u = mp[s1] - 1;<br /> int v = mp[s2] - 1;<br /> //printf("%d %d/n", u, v);<br /> d[u][v] = d[v][u] = min(d[u][v], w);<br /> }<br /> fg.clear();<br /> for (int i = 0; i < 8; i++) {<br /> scanf("%s", s1);<br /> id[i] = mp[s1] - 1;<br /> //printf("%d/n", id[i]);<br /> }<br /> steiner(n, a);<br /> // enum to find the result<br /> int i, j, z, x, y, k, b;<br /> for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)<br /> for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)<br /> for (k = 0; k < 8; k += 2)<br /> if ((i >> k & 3) == j)<br /> y += 3 << k, x = id[k];<br /> printf("%d/n",b);<br /> // TODO: cout << b << endl;<br /> }<br /> }<br />