2023 ccpc女生赛D费用流WA43

#include<bits/stdc++.h>
#define x first
#define y second
//#define int long long 
#define pb push_back
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5,M=2e5+5,INF=1e8;
int n,m,ans,a[N],q,h[N],e[M],f[M],idx,flow,cost,k;
int w[M],incf[N],S,T,pre[N],ne[M],d[N],mp[33][33];
PII ST[33],ED[33];
bool st[N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void add(int a,int b,int c,int d)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=d,f[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],w[idx]=-d,f[idx]=0,h[b]=idx++;
}
bool spfa()
{
	for(int i=0;i<=T;i++)d[i]=INF;
	memset(st,0,sizeof(st));
	memset(incf,0,sizeof(incf));
	queue<int>q;
	q.push(S),d[S]=0,incf[S]=INF;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[j]>d[t]+w[i]&&f[i])
			{
				d[j]=d[t]+w[i];
				pre[j]=i;
				incf[j]=min(incf[t],f[i]);
				if(!st[j])
				{
					st[j]=true;
					q.push(j);
				}
			}
		}
	}
	//if(100*incf[T]-d[T]<0)return false;
  //(就是上面这行，一定要加才行
	return incf[T]>0;
}
void EK()
{
	cost=0,flow=0;
	while(spfa())
	{
		int t=incf[T];
		flow+=t,cost+=t*d[T];
		for(int i=T;i!=S;i=e[pre[i]^1])
		{
			f[pre[i]]-=t;
			f[pre[i]^1]+=t;
		}
	}
}
int getr(int x,int y)
{
	return (x-1)*m+y;
}
int getc(int x,int y)
{
	return (x-1)*m+y+n*m;
}
void solve()
{
    cin>>n>>m>>k;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)cin>>mp[i][j];
	S=0,T=2*n*m+2;
	map<PII,int>aa;
	for(int i=1;i<=k;i++)
	{
		cin>>ST[i].x>>ST[i].y;
		int a=ST[i].x,b=ST[i].y;
		aa[{a,b}]=1;
		add(getr(a,b),getc(a,b),1,mp[a][b]^1);
		add(S,getr(a,b),1,0);
	}
	for(int i=1;i<=k;i++)
	{
		cin>>ED[i].x>>ED[i].y;
		int a=ED[i].x,b=ED[i].y;
		aa[{a,b}]=1;
		add(getc(a,b),T,1,0);
		add(getr(a,b),getc(a,b),1,mp[a][b]^1);
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	if(mp[i][j]!=-1)
	{
		for(int k=0;k<4;k++)
		{
			int nx=i+dx[k],ny=j+dy[k];
			if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]==-1)continue;
			add(getc(i,j),getr(nx,ny),1,0);
		}
		if(aa[{i,j}]==0)add(getr(i,j),getc(i,j),1,mp[i][j]^1);
	}
	EK();
	cout<<flow*100-cost<<'\n';
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	// int T;cin>>T;
	// while(T--)
	solve();
	return 0;
}
https://codeforces.com/gym/104725/problem/D
放个题目链接