网络流24题——骑士共存问题 luogu 3355

时间:2022-08-17 22:56:30

题目描述:这里

从这里开始,我们涉及到了一个新的问题:最小割问题

首先给出一些定义(本人根据定义自己口胡的):

一个流网络中的一个割是一个边集,使得割掉这些边集后源点与汇点不连通

而最小割问题就是一个使得边集中各边容量之和最小的割

根据ford-fulkerson定理,最小割等于最大流!

基于上面的定义,我们可以来讨论这道题了:

首先,根据套路,棋盘经过黑白染色之后可以形成一个二分图,我们由源点向黑点连边,白点向汇点连边,然后由黑点向白点连边,权值为1(所有不能用的点不做考虑)

然后跑一遍最小割,用总和减去最小割即可

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int inf=0x3f3f3f3f;
struct Edge
{
int next;
int to;
int val;
}edge[];
int head[];
int dir[][]={{,},{,},{,-},{,-},{-,-},{-,-},{-,},{-,}};
bool used[][];
int dis[];
int cur[];
int cnt=;
int n,m;
int st,ed;
void init()
{
memset(head,-,sizeof(head));
cnt=;
}
void add(int l,int r,int w)
{
edge[cnt].next=head[l];
edge[cnt].to=r;
edge[cnt].val=w;
head[l]=cnt++;
}
bool check(int x,int y)
{
return (x>=)&&(x<=n)&&(y>=)&&(y<=n)&&(!used[x][y]);
}
int ide(int x)
{
return (x&)?x+:x-;
}
int idx(int x,int y)
{
return (x-)*n+y;
}
bool bfs()
{
memset(dis,,sizeof(dis));
memcpy(cur,head,sizeof(head));
dis[st]=;
queue <int> M;
M.push(st);
while(!M.empty())
{
int u=M.front();
M.pop();
for(int i=head[u];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(edge[i].val&&!dis[to])dis[to]=dis[u]+,M.push(to);
}
}
return dis[ed];
}
int dfs(int x,int lim)
{
if(x==ed)return lim;
int ret=;
for(int i=cur[x];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(edge[i].val&&dis[to]==dis[x]+)
{
int temp=dfs(to,min(lim,edge[i].val));
if(temp)
{
lim-=temp;
ret+=temp;
edge[i].val-=temp;
edge[ide(i)].val+=temp;
if(!lim)break;
}
}
cur[x]=i;
}
return ret;
}
int dinic()
{
int ret=;
while(bfs())ret+=dfs(st,inf);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
st=n*n+,ed=n*n+;
init();
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
used[x][y]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(used[i][j])continue;
if((i+j)&)
{
add(st,idx(i,j),);
add(idx(i,j),st,);
for(int k=;k<;k++)
{
int x=i+dir[k][];
int y=j+dir[k][];
if(check(x,y))add(idx(i,j),idx(x,y),inf),add(idx(x,y),idx(i,j),);
}
}else
{
add(idx(i,j),ed,);
add(ed,idx(i,j),);
}
}
}
printf("%d\n",n*n-m-dinic());
return ;
}