YbtOJ#593-木棍问题【费用流】
2024-09-07 10:45:35
正题
题目链接:https://www.ybtoj.com.cn/contest/114/problem/3
题目大意
\(n*m\)的网格上有一些格子有木球,两个相邻木球直接可以有木棍。
两个\(L\)形的木棍会产生\(A\)的代价,两个\(I\)形的木棍会产生\(B\)的代价
对于每个\(k\)求出插入\(k\)根木棍时的最小代价。
\(n,m\in[1,40],1\leq A\leq B\leq 10^5\)
解题思路
因为\(B\geq A\)可以理解为两个相邻的木棍会产生\(A\)点代价,\(I\)形的会额外产生\(B-A\)点代价。
先不考虑\(B-A\)的部分,考虑每个点的贡献,一个点的度数为\(i\)时会产生\(\binom{i}{2}\)的贡献,并且相邻的点之间可以连边。这是一个很经典的费用流模型。
对网格黑白染色,黑色的源点连接,白色的连接汇点。对于每个连接可以分为\(4\)条边,流量都为\(1\),权值分别为\(\binom12-\binom02\ ,\ \binom22-\binom12\ ,\ \binom32-\binom22\ ,\ \binom42-\binom32\)。
这些权值递增,费用流优先流小的,所以如果流量为\(i\)那个刚好费用和就是\(\binom i2\)。
然后考虑\(I\)形的额外代价,其实就是如果一个点的横纵向度数到\(2\)就会产生代价。我们可以故技重施,对于每个点再开两个点分别表示横向/纵向,连接这些点的时候一条边权值是\(0\),另一条是\(B-A\)。
然后正常\(Ek\)费用流跑法会每次扩展一个流量,每次输出就好了。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5100,inf=2147483647/3;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct node{
int to,next,w,c;
}a[N<<5];
int op,n,m,A,B,s,t,cnt,tot=1,ans;
int f[N],mf[N],ls[N],pre[N],p[50][50];
char c[50][50];bool v[N];
queue<int>q;
void addl(int x,int y,int w,int c){
a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;
a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c;
return;
}
bool SPFA(){
memset(f,0x3f,sizeof(f));
q.push(s);f[s]=0;v[s]=1;mf[s]=inf;
while(!q.empty()){
int x=q.front();v[x]=0;q.pop();
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(!a[i].w)continue;
if(f[x]+a[i].c<f[y]){
f[y]=f[x]+a[i].c;pre[y]=i;
mf[y]=min(mf[x],a[i].w);
if(!v[y])q.push(y),v[y]=1;
}
}
}
return f[t]<inf;
}
void Updata(){
int x=t;ans+=f[t];
if(op)printf("%d\n",(ans!=0));
else printf("%d\n",ans);
while(x!=s){
a[pre[x]].w-=mf[t];
a[pre[x]^1].w+=mf[t];
x=a[pre[x]^1].to;
}
return;
}
int main()
{
freopen("trouble.in","r",stdin);
freopen("trouble.out","w",stdout);
scanf("%d",&op);op=((op>=8)&&(op<=12));
scanf("%d%d%d%d",&n,&m,&A,&B);B-=A;
for(int i=1;i<=n;i++){
scanf("%s",c[i]+1);
for(int j=1;j<=m;j++)
if(c[i][j]=='0')p[i][j]=++cnt;
}
s=3*cnt+1;t=s+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(c[i][j]=='0'){
int x=p[i][j];
if((i+j)&1){
addl(s,x*3-2,1,0); addl(s,x*3-2,1,A);
addl(s,x*3-2,1,2*A); addl(s,x*3-2,1,3*A);
addl(x*3-2,x*3-1,1,0);addl(x*3-2,x*3,1,0);
addl(x*3-2,x*3-1,1,B);addl(x*3-2,x*3,1,B);
for(int k=0;k<4;k++){
int zx=i+dx[k],zy=j+dy[k];
if(c[zx][zy]!='0')continue;
int y=p[zx][zy];
if(k<2)addl(x*3-1,y*3-1,1,0);
else addl(x*3,y*3,1,0);
}
}
else{
addl(x*3-2,t,1,0); addl(x*3-2,t,1,A);
addl(x*3-2,t,1,2*A); addl(x*3-2,t,1,3*A);
addl(x*3-1,x*3-2,1,0);addl(x*3,x*3-2,1,0);
addl(x*3-1,x*3-2,1,B);addl(x*3,x*3-2,1,B);
}
}
}
while(SPFA())
Updata();
return 0;
}
最新文章
- 自动绘图AI:程序如何画出动漫美少女
- csrf 跨站请求伪造
- 基于Node.js + jade + Mongoose 模仿gokk.tv
- 2. MySQL
- Guidelines for clock
- Java消息队列-Spring整合ActiveMq
- 虚拟机在 OpenStack 里没有共享存储条件下的在线迁移[转]
- mysql数据库误删除操作说明
- Linux系统编程----僵尸进程
- MySQL 5.7版本 sql_mode=only_full_group_by 问题
- Yii的操作提示框
- Redis分布式锁(ServiceStack.Redis实现)
- day06 元组类型
- 大白菜装机版一键制作启动u盘教程
- 用IBM MQ中间件开发碰到的MQRC_NOT_AUTHORIZED(2035)问题
- jquery 页面传值 汉字
- Ng第十课:应用机器学习的建议(Advice for Applying Machine Learning)
- 【Android】Android如何对APK反编译
- lua源代码学习(一)lua的c api外围实现
- 三值 bool? 进行与或运算后的结果