題目描述
給一個點數為N(N<50)的帶權無向圖。其中有K個景點，參觀每個景點有一個代價 Ti。有一些地方可以獲得一些景點的票，如果持票參觀景點i則代價為 FTi。 保證K<=8，FTi <= Ti。
請問從景點1出發,參觀全部的景點，再回到景點1的最小代價是多少。路的權也計算在代價中。
Trick
一個節點可能對應多個景點，也可以買到多個景點的票。
吐槽
排版無力，有神牛推薦什么好的畫圖工具(跨平臺)沒有？
而且代碼折疊以后用chrome看不了？？不是吧...
算法分析
看數據范圍比較容易想到狀態的表示：dp[Imask][Jmask][u]表示已經走過了集合為Imask的景點且拿到了集合為Jmask的票并且此時再u點的最小代價。
走到u點有兩種選擇：參觀景點or不參觀景點。拿票是免費的，所以有票一定拿。
如果一個節點對應多個景點的話，那就要參觀一起參觀。雖然這樣會忽略掉一些中間狀態，但是不影響得到最優解。
因為如果在u我最后參觀景點j，那么可以選擇在參觀j的時候一起參觀其他景點。
根據這兩種決策，我們可以很容易的得到兩個轉移方程dp[NewImask][NewJmask][v] = dp[Imask][Jmask][u] + way[u][v] + cost;
dp[Imask][NewJmask][v] = dp[Imask][Jmask][u] + way[u][v] ;
這兩個方程當前兩維不等的時候，都有比較明確的轉移順序。否則的話就沒有明確的轉移順序，所以需要floyed預先處理一下最短路。
有一個小小的優化： 如果景點K已經被參觀了，那么對K有票無票都無所謂了。所以同一標記為有票。這樣可以剪掉1/4的狀態。
最后的復雜度就是O(3^K*n^3)。4.6s AC。
#include<iostream>
#include<bitset>
#include<cstdio>
#include<string>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
#define re(i,n) for(int i=0;i<n;i++)
#define re1(i,n) for(int i=1;i<=n;i++)
#define re2(i,n) for(int i=0;i<=n;i++)
#define re3(i,n) for(int i=1;i<n;i++)
#define clr(a,n) memset(a,n,sizeof(a))
#define debug(n) cout<<#n<<"="<<n<<end
inline bool _1(int mask , int i) {return mask & (1 << i);}
template <typename T> inline void chkmin(T &a,const T b){if(b < a) a = b;}
template <typename T> inline void chkmax(T &a,const T b){if(b > a) a = b;}
const int N = 55;
const int inf = ~0u>>2;
const int xinf = ~0u>>1;
const int M = 8;
int num[N][N];
int dp[1 << M][1 << M][N];
int ft[N], T[N];
int G[N][M+1];
int Gtk[N][M+1];
int main(){
int n,m,k,t;
cin >> t;
re(ooo,t){
scanf("%d%d%d",&n,&m,&k);
int u,v,c;
re2(i,n) re2(j,n) num[i][j] = i==j ? 0 : inf;
re(i,m) {
scanf("%d%d%d",&u,&v,&c);
chkmin(num[u][v],c);
chkmin(num[v][u],c);
}
re1(p,n) re1(i,n) re1(j,n) chkmin(num[i][j] , num[i][p] + num[p][j]);
num[0][1] = 0;
clr(Gtk,0); clr(G,0);
int mask = 1 << k;
re(i,k){
scanf("%d",&u);
G[u][i] = 1;
scanf("%d%d",&T[i],&ft[i]);
int tm;
scanf("%d",&tm);
while(tm--){
scanf("%d",&v);
Gtk[v][i] = 1;
}
}
re(i,mask) re(j,mask) re2(p,n) dp[i][j][p] = xinf;
dp[0][0][0] = 0;
re(imsk,mask) re(jmsk,mask) if((imsk & jmsk) == imsk)
re2(u,n) if(dp[imsk][jmsk][u] < xinf){
re1(v,n) if(u!=v && G[u][v] < inf){
int isk = imsk , jsk = jmsk;
re(i,k) if(G[v][i]) isk |= 1 << i;
re(i,k) if(Gtk[v][i]) jsk |= 1 << i;
int val = dp[imsk][jmsk][u] + num[u][v];
chkmin(dp[imsk][jsk][v],val);
re(i,k) if(_1(imsk,i) == 0 && _1(isk,i)){
val += _1(jsk,i) ? ft[i]: T[i];
}
jsk |= isk;
chkmin(dp[isk][jsk][v], val);
}
}
int ans = dp[mask-1][mask-1][1];
printf("Case #%d: %d\n",ooo+1,ans);
}
}
1 #include<iostream>
2 #include<bitset>
3 #include<cstdio>
4 #include<string>
5 #include<cassert>
6 #include<cstdlib>
7 #include<cstring>
8 #include<queue>
9 using namespace std;
10 #define re(i,n) for(int i=0;i<n;i++)
11 #define re1(i,n) for(int i=1;i<=n;i++)
12 #define re2(i,n) for(int i=0;i<=n;i++)
13 #define re3(i,n) for(int i=1;i<n;i++)
14 #define clr(a,n) memset(a,n,sizeof(a))
15 #define debug(n) cout<<#n<<"="<<n<<end
16 inline bool _1(int mask , int i) {return mask & (1 << i);}
17 template <typename T> inline void chkmin(T &a,const T b){if(b < a) a = b;}
18 template <typename T> inline void chkmax(T &a,const T b){if(b > a) a = b;}
19 const int N = 55;
20 const int inf = ~0u>>2;
21 const int xinf = ~0u>>1;
22 const int M = 8;
23 int num[N][N];
24 int dp[1 << M][1 << M][N];
25 int ft[N], T[N];
26 int G[N][M+1];
27 int Gtk[N][M+1];
28 int main(){
29 int n,m,k,t;
30 cin >> t;
31 re(ooo,t){
32 scanf("%d%d%d",&n,&m,&k);
33 int u,v,c;
34 re2(i,n) re2(j,n) num[i][j] = i==j ? 0 : inf;
35 re(i,m) {
36 scanf("%d%d%d",&u,&v,&c);
37 chkmin(num[u][v],c);
38 chkmin(num[v][u],c);
39 }
40 re1(p,n) re1(i,n) re1(j,n) chkmin(num[i][j] , num[i][p] + num[p][j]);
41 num[0][1] = 0;
42 clr(Gtk,0); clr(G,0);
43 int mask = 1 << k;
44 re(i,k){
45 scanf("%d",&u);
46 G[u][i] = 1;
47 scanf("%d%d",&T[i],&ft[i]);
48 int tm;
49 scanf("%d",&tm);
50 while(tm--){
51 scanf("%d",&v);
52 Gtk[v][i] = 1;
53 }
54 }
55 re(i,mask) re(j,mask) re2(p,n) dp[i][j][p] = xinf;
56 dp[0][0][0] = 0;
57 re(imsk,mask) re(jmsk,mask) if((imsk & jmsk) == imsk)
58 re2(u,n) if(dp[imsk][jmsk][u] < xinf){
59 re1(v,n) if(u!=v && G[u][v] < inf){
60 int isk = imsk , jsk = jmsk;
61 re(i,k) if(G[v][i]) isk |= 1 << i;
62 re(i,k) if(Gtk[v][i]) jsk |= 1 << i;
63 int val = dp[imsk][jmsk][u] + num[u][v];
64 chkmin(dp[imsk][jsk][v],val);
65 re(i,k) if(_1(imsk,i) == 0 && _1(isk,i)){
66 val += _1(jsk,i) ? ft[i]: T[i];
67 }
68 jsk |= isk;
69 chkmin(dp[isk][jsk][v], val);
70 }
71 }
72 int ans = dp[mask-1][mask-1][1];
73 printf("Case #%d: %d\n",ooo+1,ans);
74 }
75 }
76 posted on 2012-04-24 20:11
西月弦 閱讀(1812)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告