算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述

   给一个点数为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);
}
}

posted on 2012-04-24 20:11 西月弦 阅读(1554) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理