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 閱讀(606)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc