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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2668][cqoi2012]交换棋子  

2015-02-02 21:38:24|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2668: [cqoi2012]交换棋子

算法类型还是比较容易猜的
重搞了三次才过样例……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N = 20+5;
const int MAX = 1E9;
const int P = N*N*2;
const int M = P*10;
const int dir[8][2] = {{0,1},{0,-1},{-1,0},{1,0},{1,1},{-1,1},{1,-1},{-1,-1}};
short map[N][N];
int n,m,G,large,start,end,T,all[2];
struct Edge{
int from,to,cap,flow,cost;
Edge(int f=0,int t=0,int c=0,int fl=0,int co=0){from=f;to=t;cap=c;flow = fl;cost = co;}
}edges[M];
struct Point{
Point(){next = NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->d = a;
l->next = next;next = l;
}
}point[P];
int dis[P],fa[P],flows[P];short v[P];
queue<int>dui;
bool spfa(int &flow,int &cost){
for(int i=1;i<=large;i++)dis[i] = MAX;
dis[start] = 0;
dui.push(start);
flows[start] = MAX;
v[start] = 1;
while(!dui.empty()){
int now = dui.front();dui.pop();
//if(now == 5) now = 5;
for(Point *i = point[now].next;i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(e.cap > e.flow && dis[e.to] > dis[now] + e.cost){
dis[e.to] = dis[now] + e.cost;
flows[e.to] = min(flows[now],e.cap - e.flow);
fa[e.to] = i->d;
if(!v[e.to]){
v[e.to] = 1;
dui.push(e.to);
}
}
}v[now]=0;
}
if(dis[end] == MAX)return 0;
flow += flows[end];
cost += flows[end]*dis[end];
int now = end;
while(now!=start){
Edge &e = edges[fa[now]];
e.flow += flows[end];
edges[fa[now]^1].flow -= flows[end];
now = e.from;
}
return 1;
}
int calc(int i,int j,int k){return (i-1)*m+j + (k-1)*G;}
void AddEdge(int from,int to,int cap,int cost){
point[from].push(T);
edges[T++] = Edge(from,to,cap,0,cost);
point[to].push(T);
edges[T++] = Edge(to,from,0,0,-cost);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;char cc;
scanf("%d%d",&n,&m);
G = n*m;
//start = G*4+1;large = end = start + 1;
start = G*2+1;large = end = start + 1;
/*
for(int k=1;k<=4;k++)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
printf("%d ",calc(i,j,k));
}printf("\n");*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
map[i][j] += cc-'0';
/*
if(cc=='1')AddEdge(start,calc(i,j,1),1,0),
AddEdge(calc(i,j,1),calc(i,j,4),1,0),
AddEdge(calc(i,j,1),calc(i,j,2),1,0),all[0]++;*/
if(cc=='1')AddEdge(start,calc(i,j,1),1,-1),all[0]++;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
map[i][j] += cc-'0';
/*
if(cc=='1')AddEdge(calc(i,j,4),end,1,0),
AddEdge(calc(i,j,3),calc(i,j,4),1,0),all[1]++;*/
if(cc=='1')AddEdge(calc(i,j,2),end,1,-1),all[1]++;
}
if(all[0]!=all[1]){printf("-1\n");return 0;}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);

//if(cc!='0')AddEdge(calc(i,j,2),calc(i,j,3),cc-'0',1);
AddEdge(calc(i,j,1),calc(i,j,2),(cc-'0'+map[i][j])/2,2);
for(int k=0;k<8;k++){//8
int x,y;
x = i+dir[k][0];y = j+dir[k][1];
if(x<1||x>n||y<1||y>m)continue;
//AddEdge(calc(i,j,3),calc(x,y,2),MAX,0);
AddEdge(calc(i,j,2),calc(x,y,1),MAX,0);
}
}
int flow,cost;flow=cost=0;
while(spfa(flow,cost));
//for(i=1;i<=large;i++)if(dis[i]!=MAX)printf("%d ",dis[i]);else printf("M ");printf("\n");
//printf("%d\n",flow);
if(flow != all[0]){printf("-1\n");return 0;}
printf("%d\n",cost/2);
return 0;
}

题解:
费用流。
· 首先把每个点拆点,然后把每个格子看成一个“交换站”,把初始图的1看成一个"入",把目标图的1看成一个“出”
那么问题就是流从入到出经过一些交换站,使得交换站被经过的次数最少。
我们认为流不能在交换站停留,所以流经过交换站一定是会付出代价2:交换进来一次,交换出去一次。
然后注意有“出”或者“入”的点比较特殊,因为这个点必然要经过自己的交换站一次,而且这次经过是不需要代价的,
所以把每个位置拆成点1和2,连边1->2容量是:(可交换次数+[这个点是“入”]+[这个点是“出”])/2,费用是2。
如果这个点是入,那么S->1容量是1,费用是-1
如果这个点是出,那么2->T容量是1,费用是-1
最后注意判一下无解,问题解决。
  评论这张
 
阅读(271)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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