BZOJ 1324 Exca神剑 最小割

时间:2021-07-18 09:08:18

标题效果:给定一个n*m矩阵。所有的格宝石之子,人们可选择起始位置,后除去宝石的当前位置的周围消失,然后你就可以走两步,重复上述过程

easy发现格儿子把它周围格孩子不能拿 因此,党格访问问题

黑白染色 黑色点连源 白色点连汇 流量为格子的权值 黑白之间连边 流量为正无穷 用总和减去最大流就是答案

曾经写的EK 跑了4000+ms我也是醉了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 110
#define MAX (0x7fffffff)
int m,n,sum,ans;
struct abcd{int x,y,f,next;}table[100100];int head[M][M],tot=1;
void addd(int x,int y,int tox,int toy,int f)
{
table[++tot].x=tox;
table[tot].y=toy;
table[tot].f=f;
table[tot].next=head[x][y];
head[x][y]=tot;
}
void add(int x,int y,int tox,int toy,int f){ addd(x,y,tox,toy,f);addd(tox,toy,x,y,0); }
inline int min(int x,int y){ return x<y?x:y; }
struct que{int x,y;}q[65540];unsigned short r,h;
int f[M][M],from[M][M];
bool maxflow()
{
int i;
memset(f,0,sizeof f);
q[++h].x=0;q[h].y=0;
f[0][0]=MAX;
while(r!=h)
{
r++;
for(i=head[q[r].x][q[r].y];i;i=table[i].next)if(table[i].f)if(!f[table[i].x][table[i].y])
{
f[table[i].x][table[i].y]=min(f[q[r].x][q[r].y],table[i].f);
from[table[i].x][table[i].y]=i;
q[++h].x=table[i].x;q[h].y=table[i].y;
}
}
if(!f[0][1])return 0;
ans+=f[0][1];
for(i=from[0][1];i;i=from[table[i^1].x][table[i^1].y])table[i].f-=f[0][1],table[i^1].f+=f[0][1];
return 1;
}
int main()
{
int i,j,x;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&x);
sum+=x;
if(i+j&1)add(i,j,0,1,x);
else
{
add(0,0,i,j,x);
if(i^1)add(i,j,i-1,j,MAX);
if(j^1)add(i,j,i,j-1,MAX);
if(i^m)add(i,j,i+1,j,MAX);
if(j^n)add(i,j,i,j+1,MAX);
}
}
while(maxflow());
printf("%d",sum-ans);
}

版权声明:本文博主原创文章。博客,未经同意不得转载。