BZOJ2668: [cqoi2012]交换棋子(费用流)
2024-08-31 16:08:20
Description
有一个n行m列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
Input
第一行包含两个整数n,m(1<=n, m<=20)。以下n行为初始状态,每行为一个包含m个字符的01串,其中0表示黑色棋子,1表示白色棋子。以下n行为目标状态,格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串,表示每个格子参与交换的次数上限。
Output
输出仅一行,为最小交换总次数。如果无解,输出-1。
Sample Input
3 3
110
000
001
000
110
100
222
222
222
110
000
001
000
110
100
222
222
222
Sample Output
4
解题思路:
这道题可以发现费用流肯定是可以解决的。
问题是怎么建图。
易知每步交换一定是一黑一白。
所以就可以考虑每个点前后的变化来得到白变黑次数的上限。
这个只与前后黑白状态有关。
若状态相同,则白变黑次数=黑变白次数。
不同则讨论即可。
一定是一个比另外一个大一。
这样就可以确定流入和流出上限。
现在考虑流量守恒,发现白黑相同时无流量变化,黑白不同时边权也守恒。
发现这样只需要新建两个新节点来达到建图的目的。
代码:
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const int oo=0x3f3f3f3f;
const int di[]={,,-,,,,-,-};
const int dj[]={-,,,,-,,,-};
struct pnt{
int hd;
int dis;
int val;
int pre;
int lst;
bool vis;
}p[];
struct ent{
int twd;
int lst;
int vls;
int dis;
}e[];
int cnt;
int n,m;
int s,t;
int maxflow;
int no[][];
int st[][];
int ed[][];
int vl[][];
std::queue<int>Q;
void ade_(int f,int t,int v,int d)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].dis=d;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void adde(int f,int t,int v,int d)
{
ade_(f,t,v,d);
ade_(t,f,,-d);
return ;
}
bool Spfa(void)
{
while(!Q.empty())Q.pop();
for(int i=;i<=t;i++)
{
p[i].dis=p[i].val=oo;
p[i].pre=-;
p[i].vis=false;
}
Q.push(s);
p[s].vis=true;
p[s].dis=;
while(!Q.empty())
{
int x=Q.front();
Q.pop();
p[x].vis=false;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].dis>p[x].dis+e[i].dis&&e[i].vls)
{
p[to].dis=p[x].dis+e[i].dis;
p[to].pre=x;
p[to].lst=i;
p[to].val=std::min(p[x].val,e[i].vls);
if(p[to].vis)continue;
p[to].vis=true;
Q.push(to);
}
}
}
return p[t].pre!=-;
}
int Ek(void)
{
int ans=;
while(Spfa())
{
maxflow+=p[t].val;
ans+=p[t].dis*p[t].val;
for(int i=t;i!=s;i=p[i].pre)
{
e[p[i].lst].vls-=p[t].val;
e[((p[i].lst-)^)+].vls+=p[t].val;
}
}
return ans;
}
int main()
{
int a1(),a2();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)for(int j=;j<=m;j++)no[i][j]=++cnt;
s=cnt*+,t=s+;
cnt=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%1d",&st[i][j]),a1+=st[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%1d",&ed[i][j]),a2+=ed[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%1d",&vl[i][j]);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(!st[i][j])adde(s,no[i][j],,);
if(!ed[i][j])adde(no[i][j],t,,);
int frm,twd;
if(st[i][j]==ed[i][j])frm=twd=vl[i][j]/;
if(st[i][j]>ed[i][j])frm=(vl[i][j]+)/,twd=vl[i][j]/;
if(st[i][j]<ed[i][j])twd=(vl[i][j]+)/,frm=vl[i][j]/;
adde(no[i][j]+n*m,no[i][j],frm,);
adde(no[i][j],no[i][j]+*n*m,twd,);
for(int d=;d<;d++)
{
int ii=di[d]+i;
int jj=dj[d]+j;
if(!no[ii][jj])continue;
adde(no[i][j]+*n*m,no[ii][jj]+m*n,oo,); }
}
}
int ans=Ek();
if(m*n-maxflow!=a1||a1!=a2)ans=-;
printf("%d\n",ans);
return ;
}
最新文章
- Oracle组合索引与回表
- 从excel文件中获取数据(2)
- 点透 &; 解决方案
- C++11静态assert
- js 格式化数字
- Zabbix实战-简易教程(5)--Proxy和Agent端(源码和yum方式)
- 学习pthreads,使用互斥量进行同步
- JMeter Ultimate Thread Group阶梯式减压
- MATLAB绘图功能(2) 二维底层绘图修饰
- java_16Arrays类
- git 先创建远程库后克隆到本地
- linux hostname 命令 显示当前主机域名 /etc/hostname
- linux学习第一天 (Linux就该这么学) 找到一本不错的Linux电子书,附《Linux就该这么学》章节目录
- JAVA框架 Spring 入门
- Struts2学习笔记四:深入拦截器
- 1001.A+B Format (20) 解题
- 下载windows版本apache网页服务器
- JS中深拷贝数组、对象、对象数组方法
- logstash通过redis收集日志
- 【转】crontab命令 脚本定时运行
热门文章
- jQuery -&;gt; 怎样【先创建、再改动、后加入】 DOM元素
- c++ string类的完整实现!!!
- UVALive 6084 Happy Camper(数学题)
- 二维码框架ZBarSDK的使用和自己定义二维码扫描界面方法
- Visual Assist X 10.8.2036的Crack破解补丁.2014.05.22 (General release.)
- HDU 5274(LCA + 线段树)
- H5学习_番外篇_PHP数据库操作
- codevs1052
- reverse(两种反向生成url django原生形式和rest_framework中版本的形式)
- Android5.0之后的页面切换动画