注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2479 迷宫改造  

2014-01-16 09:28:31|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我的WC之旅最后一题
第一眼看上去觉得是裸的斯坦纳树
但是不知道有向图上能不能搞斯坦纳树

问vfk,vfk也不知道有向图能不能搞……
注意到有关系的人只有三对
虽然不知道这个3的原意是不是让你斯坦纳树的
不过vfk告诉我说既然只有3………………
直接分情况讨论阿

好,我们开始人脑爆枚最优方案
首先用斯坦纳树我们可以求出f[x][y][status],g[x][y][status]分别表示status状态的起点走到(x,y)处的最短路与(x,y)走到status状态的终点的最短距离
情况1:
只有一对人
我们直接输出
情况2:
两对人
分别走与min{f[x][y][3]+g[x][y][3]}
情况3:
三对人
方案3.1:
f[ed[0][0]][ed[0][1]]+f[ed[1][0]][ed[1][1]]+f[ed[2][0]][ed[2][1]],即分别走到终点
方案3.2:
min{f[x][y][7]+g[x][y][7]},汇集到一起然后走到终点
情况3.3:
由于接下来会经常出现“某两人”的字眼,我们不妨3!爆枚他们的映射
甲乙汇合,甲和乙分开之后甲跑到终点了……乙继续一个人走着忽然有一天它看到了丙于是不再孤单……然后乙和丙又各自跑到自己终点去了
dp[x][y][0]表示在甲乙一起走着一段的最优解……dp[x][y][1]表示分开之后乙一个人的最优解
答案是min(dp[x][y][1]+丙走到(x,y)加上g[x][y][乙丙])
显然dp[x][y][0]=f[x][y][甲乙]
所以实现的时候我们只用设dp[x][y]表示这里的dp[x][y][1]
dp[x][y]=min{dp[x'][y']+cost(x',y',x,y),f[x'][y'][甲乙]+g[x'][y'][甲]+cost(x',y',x,y)}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define INF 1000000
#define maxn 25
using namespace std;
struct Node
{
int x,y,s;
Node() {}
Node(int x,int y,int s): x(x),y(y),s(s) {}
};
queue<Node> Q;
int nRow,nCol;
int st[3][2],ed[3][2],n;
int movex[]={1,0,0,-1};
int movey[]={0,1,-1,0};
int map[maxn][maxn][4];
int bit_st[maxn][maxn],bit_ed[maxn][maxn];
int f[maxn][maxn][1<<3],g[maxn][maxn][1<<3];
int ans[maxn][maxn][3];
int S;
void read()
{
int nDoor;
cin>>nRow>>nCol>>nDoor;
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
for(int k=0;k<4;++k)
map[i][j][k]=1;
for(int i=1,a,b,c,d;i<=nDoor;++i)
{
cin>>a>>b>>c>>d;
for(int j=0;j<4;++j)
{
int px,py;
px=a+movex[j],py=b+movey[j];
if(px==c&&py==d)
map[a][b][j]=0;
px=c+movex[j],py=d+movey[j];
if(px==a&&py==b)
map[c][d][j]=0;
}
}
cin>>n;
S=(1<<n)-1;
for(int i=0;i<n;++i)
{
cin>>st[i][0]>>st[i][1]>>ed[i][0]>>ed[i][1];
bit_st[st[i][0]][st[i][1]]=1<<i;
bit_ed[ed[i][0]][ed[i][1]]=1<<i;
}
}
int work()
{
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
{
for(int k=1;k<=S;++k)
f[i][j][k]=g[i][j][k]=INF;
f[i][j][bit_st[i][j]]=0;
g[i][j][bit_ed[i][j]]=0;
}
static bool use[maxn][maxn][1<<3];
for(int s=1;s<=S;++s)
{
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
if(bit_st[i][j]==0||(s&bit_st[i][j]))
{
for(int k=(s-1)&s;k;k=(k-1)&s)
f[i][j][s]=min(f[i][j][s],f[i][j][k|bit_st[i][j]]+f[i][j][(s^k)|bit_st[i][j]]);
if(f[i][j][s]!=INF)
Q.push(Node(i,j,s)),use[i][j][s]=true;
}
Node p;
while(!Q.empty())
{
p=Q.front(),Q.pop(),use[p.x][p.y][p.s]=false;
for(int i=0;i<2;++i)
{
int px=p.x+movex[i],py=p.y+movey[i],ps=p.s|bit_st[px][py];
if(f[px][py][ps]>f[p.x][p.y][p.s]+map[p.x][p.y][i])
{
f[px][py][ps]=f[p.x][p.y][p.s]+map[p.x][p.y][i];
if(use[px][py][ps]==false)
Q.push(Node(px,py,ps)),use[px][py][ps]=true;
}
}
}
}
for(int s=1;s<=S;++s)
{
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
if(bit_ed[i][j]==0||(s&bit_ed[i][j]))
{
for(int k=(s-1)&s;k;k=(k-1)&s)
g[i][j][s]=min(g[i][j][s],g[i][j][k|bit_ed[i][j]]+g[i][j][(s^k)|bit_ed[i][j]]);
if(g[i][j][s]!=INF)
Q.push(Node(i,j,s)),use[i][j][s]=true;
}
Node p;
while(!Q.empty())
{
p=Q.front(),Q.pop(),use[p.x][p.y][p.s]=false;
for(int i=2;i<4;++i)
{
int px=p.x+movex[i],py=p.y+movey[i],ps=p.s|bit_ed[px][py];
if(g[px][py][ps]>g[p.x][p.y][p.s]+map[p.x][p.y][i])
{
g[px][py][ps]=g[p.x][p.y][p.s]+map[p.x][p.y][i];
if(use[px][py][ps]==false)
Q.push(Node(px,py,ps)),use[px][py][ps]=true;
}
}
}
}
if(n==1)
return f[ed[0][0]][ed[0][1]][1];
else if(n==2)
{
int ans=f[ed[0][0]][ed[0][1]][1]+f[ed[1][0]][ed[1][1]][2];
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
ans=min(ans,f[i][j][3]+g[i][j][3]);
return ans;
}
else
{
int ans=f[ed[0][0]][ed[0][1]][1]+f[ed[1][0]][ed[1][1]][2]+f[ed[2][0]][ed[2][1]][4];
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
ans=min(ans,f[i][j][7]+g[i][j][7]);
static int a[5],dp[maxn][maxn];
a[1]=1,a[2]=2,a[3]=4;
for(int T=1;T<=6;++T)
{
next_permutation(a+1,a+4);
for(int i=1;i<=nRow;++i)
for(int j=1;j<=nCol;++j)
{
dp[i][j]=INF;
for(int k=2;k<4;++k)
{
int px=i+movex[k],py=j+movey[k];
if(px>=1&&py>=1)
{
dp[i][j]=min(dp[i][j],dp[px][py]+map[i][j][k]);
dp[i][j]=min(dp[i][j],f[px][py][a[1]|a[2]]+map[i][j][k]+g[px][py][a[1]]);
}
}
ans=min(ans,dp[i][j]+f[i][j][a[3]]+g[i][j][a[2]|a[3]]);
}
}
return ans;
}
}
int main()
{
read();
cout<<work()<<endl;
return 0;
}

  评论这张
 
阅读(561)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017