晓天动漫

Coding yy life……

HNU 10862 Ticket to Ride

最小斯泰纳树,直接用吉大模板

 1 /* 
 2  * File:   HNU 10862 Ticket to Ride
 3  * Author: xiaotian @ hnu
 4  * Created on 2010年10月6日, 下午7:48
 5  * 题解:最小斯泰纳树,直接套板
 6  */
 7 
 8 #include<stdio.h>
 9 #include<iostream>
10 #include<string>
11 #include<queue>
12 #include<map>
13 #include<set>
14 #include<math.h>
15 using namespace std;
16 #define N 1000
17 #define A 8
18 #define inf 0x7ffffff
19 int vis[N], id[A]; //id[]: A中点的标号
20 int d[N][N], dp[1 << A][N]; //dp[i][v]: 点v到点集i的最短距离
21 map<stringint>mp, fg;
22 
23 int min(int a, int b) {
24     return a < b ? a : b;
25 }
26 
27 void steiner(int n, int a) {
28     int i, j, k, mx, mk, top = (1 << a);
29     for (k = 0; k < n; k++)
30         for (i = 0; i < n; i++)
31             for (j = 0; j < n; j++)
32                 if (d[i][j] > d[i][k] + d[k][j])
33                     d[i][j] = d[i][k] + d[k][j];
34     for (i = 0; i < a; i++) { // vertex: 0 ~ n-1
35         for (j = 0; j < n; j++)
36             dp[1 << i][j] = d[j][ id[i] ];
37     }
38     for (i = 1; i < top; i++) {
39         if (0 == (i & (i - 1))) continue;
40         memset(vis, 0sizeof (vis));
41         for (k = 0; k < n; k++) { // init
42             for (dp[i][k] = inf, j = 1; j < i; j++)
43                 if ((i | j) == i &&
44                         dp[i][k] > dp[j][k] + dp[i - j][k])
45                     dp[i][k] = dp[j][k] + dp[i - j][k];
46         }
47         for (j = 0; mx = inf, j < n; j++) { // update
48             for (k = 0; k < n; k++)
49                 if (dp[i][k] <= mx && 0 == vis[k])
50                     mx = dp[i][mk = k];
51             for (k = 0, vis[mk] = 1; k < n; k++)
52                 if (dp[i][mk] > dp[i][k] + d[k][mk])
53                     dp[i][mk] = dp[i][k] + d[k][mk];
54         }
55     }
56 }
57 
58 int main() {
59     int n, m, a = 8, w;
60     char s1[25], s2[25];
61     while (scanf("%d%d\n"&n, &m) != EOF) {
62         if (n == 0 && m == 0return 0;
63         mp.clear();
64         for (int i = 0; i < n; i++) {
65             scanf("%s",s1);
66             mp[s1] = i + 1;
67         }
68         for (int i = 0; i <= n; i++)
69             for (int j = 0; j <= n; j++) d[i][j] = i==j?0:inf;
70         for (int i = 0; i < m; i++) {
71             scanf("%s %s %d", s1, s2, &w);
72             int u = mp[s1] - 1;
73             int v = mp[s2] - 1;
74             d[u][v] = d[v][u] = min(d[u][v], w);
75         }
76         fg.clear();
77         for (int i = 0; i < 8; i++) {
78             scanf("%s", s1);
79             id[i] = mp[s1] - 1;
80         }
81         steiner(n, a);
82         int i, j, z, x, y, k, b;
83         for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)
84             for (j = 0; y = 0, j < 4; z += !!* dp[y][x], j++)
85                 for (k = 0; k < 8; k += 2)
86                     if ((i >> k & 3== j)
87                         y += 3 << k, x = id[k];
88         printf("%d\n",b);
89     }
90 }


posted on 2010-10-06 20:57 晓天_xiaotian 阅读(282) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿

随笔分类

随笔档案

相册

收藏夹

ACM Online Judge

搜索

最新评论

阅读排行榜

评论排行榜