拿这个题复习一下自己的Dinic板子

然后发现自己只有60分qwq然而建模应该没有问题吧

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

#define next aya

const int inf=1145141919;

int n,m,head[100050],tail[100050],next[100050],r[100050],ecnt=1,s=0,t,d[10050],cur[10050],flow,cost,id[105][105];

inline void link(int u,int v,int w)
{
	next[++ecnt]=head[u];
	head[u]=ecnt;
	tail[ecnt]=v;
	r[ecnt]=w;
	next[++ecnt]=head[v];
	head[v]=ecnt;
	tail[ecnt]=u;
	r[ecnt]=0;
}

inline bool BFS()
{
	queue <int> q;
	q.push(t);
	memset(d,0,sizeof(d));
	d[t]=1;
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=head[u];i;i=next[i])
		{
			int v=tail[i];
			if (d[v]==0 && r[i^1]>0)
			{
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return d[s]>0;
}

inline int DFS(int u,int budget)
{
	if (u==t)
		return budget;
	int res=0;
	for (int &e=cur[u];e;e=next[e])
	{
		int v=tail[e];
		if (d[v]+1==d[u] && r[e]>0)
		{
			int delta=DFS(v,min(r[e],budget));
			if (delta)
			{
				r[e]-=delta;
				r[e^1]+=delta;
				flow+=delta;
				budget-=delta;
				return delta;
			}
		}
	}
	return 0;
}

inline int Dinic()
{
	int ans=0;
	while (BFS())
	{
		for (int i=s;i<=t;i++)
			cur[i]=head[i];
		ans+=DFS(s,1145141919);
	}
	return ans;
}

int a[105][105];

int main()
{
	n=read(),m=read();
	t=n*m+1;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			id[i][j]=(i-1)*m+j;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			a[i][j]=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==1)
				link(s,id[i][j],1145141919);
			if (a[i][j]==2)
				link(id[i][j],t,1145141919);
		}
	const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			for (int k=0;k<4;k++)
			{
				int nx=i+dx[k],ny=j+dy[k];
				if (nx>=1 && ny>=1 && nx<=n && ny<=m)
					link(id[i][j],id[nx][ny],1);
			}
	cout << Dinic() << endl;
	return 0;
}