http://acm.hdu.edu.cn/showproblem.php?pid=3311
给定6个基础点，和1000个辅助点，以及无向边若干。
求一棵代价最小的生成子树，使得6个基础点连通。
http://en.wikipedia.org/wiki/Steiner_tree_problem
方法一：
状态DP。
一棵树，实际上可以看成是由两棵子树拼接而成，或者一棵树扩展一条边筛选。而要完整地表示一棵子树，需要记录它的根，和对6个基础点的覆盖状态。
这样求一棵大树，可以枚举接合点，以及两个子树的覆盖状态。
若dp[i][j]，i表示接合点，j表示覆盖状态，那么dp[i][j]=min{dp[i][k]+dp[i][j^k]}。
直接扩展一条边, 可以在保持j不变的情况下, 优先队列广搜, 大大降低复杂度.
方法二：
spfa。
dp[i][j]意义同上。一个点(i,j)，对每个邻接点i'，枚举那一头的状态j'，然后用dp[i][j]+dp[i'][j']+way[i][i']去更新dp[i][j|j']和dp[i'][j|j']。
ps. topcoder srm 470 div1 level3是此题升级版.
1 #include <string>
2 #include <vector>
3 #include <list>
4 #include <map>
5 #include <queue>
6 #include <stack>
7 #include <set>
8 #include <iostream>
9 #include <sstream>
10 #include <numeric>
11 #include <algorithm>
12 #include <cmath>
13 #include <cctype>
14 #include <cstdlib>
15 #include <cstdio>
16 #include <cstring>
17 using namespace std;
18
19 #define CLR(x) memset((x),0,sizeof(x))
20 #define SET(x,y) memset((x),(y),sizeof(x))
21 #define REP(i,x) for(int i=0;i<(x);i++)
22 #define FOR(i,x,y) for(int i=(x);i<(y);i++)
23 #define VI vector<int>
24 #define PB(i,x) (i).push_back(x)
25 #define MP(x,y) make_pair((x),(y))
26
27 struct EDGE{
28 int v,e,d;
29 }edg[20000];
30 int ecnt, gg[1006];
31
32 struct HEAP{
33 int v,d;
34 void set(int nv, int nd){v=nv;d=nd;}
35 }hp[1006*(1<<6)*10];
36 int sz;
37 bool vis[1006];
38
39 int dp[1006][1<<6];
40 int N, M, P;
41
42 bool cmp(const HEAP &a, const HEAP &b)
43 { return a.d>b.d; }
44
45 void addedge(int u, int v, int d)
46 {
47 edg[ecnt].v=v; edg[ecnt].d=d; edg[ecnt].e=gg[u]; gg[u]=ecnt++;
48 edg[ecnt].v=u; edg[ecnt].d=d; edg[ecnt].e=gg[v]; gg[v]=ecnt++;
49 }
50
51 int steiner()
52 {
53 int up = 1<<(N+1);
54 SET(dp,-1);
55 REP(i,N+1) dp[i][1<<i]=0;
56 FOR(i,N+1,N+M+1) dp[i][0]=0;
57 REP(i,up){
58 REP(j,N+M+1){
59 for(int k=i; k>0; k=(k-1)&i){
60 if(dp[j][k]!=-1 && dp[j][i^k]!=-1)
61 if(dp[j][i]==-1 || dp[j][i]>dp[j][k]+dp[j][i^k])
62 dp[j][i]=dp[j][k]+dp[j][i^k];
63 }
64 }
65 sz=0;
66 CLR(vis);
67 REP(j,N+M+1) if(dp[j][i]!=-1){
68 hp[sz++].set(j,dp[j][i]);
69 push_heap(hp, hp+sz, cmp);
70 }
71 while(sz){
72 int now=hp[0].v;
73 pop_heap(hp, hp+sz--,cmp);
74 if(vis[now])continue;
75 vis[now]=true;
76 for(int e=gg[now]; ~e; e=edg[e].e){
77 int to=edg[e].v, td=dp[now][i]+edg[e].d;
78 if(dp[to][i]==-1 || dp[to][i]>td){
79 dp[to][i]=td;
80 hp[sz++].set(to,td);
81 push_heap(hp, hp+sz, cmp);
82 }
83 }
84 }
85 }
86 return dp[0][up-1];
87 }
88
89 int main()
90 {
91 while(~scanf("%d %d %d", &N, &M, &P)){
92 int u, v, d;
93 SET(gg,-1); ecnt=0;
94 REP(i,N+M){
95 scanf("%d", &d);
96 addedge(0,i+1, d);
97 }
98 REP(i,P){
99 scanf("%d %d %d", &u, &v, &d);
100 addedge(u,v,d);
101 }
102 int ret=steiner();
103 printf("%d\n", ret);
104 }
105 return 0;
106 }
posted on 2010-05-27 16:21
wolf5x 阅读(584)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc