C++ 解法, 执行用时: 51ms, 内存消耗: 6528K, 提交时间: 2021-09-27 16:11:21

#include<bits/stdc++.h>
using namespace std;
const int N=205*205;
const int M=N*6;
int n,m,c,x,y,z,tot=1,num,s,t,ans,last[N],d[N],co[N],cur[N],fx[4][2]={0,1,0,-1,1,0,-1,0};
bool bz[205][205];
struct cost
{
	int to,nex,flow;
}e[M+M];
int min(int a,int b){return a<b?a:b;}
int get(int x,int y)
{
	return (x-1)*n+y;
}
void add(int x,int y,int z)
{
	e[++tot]=(cost){y,last[x],z},last[x]=tot;
	e[++tot]=(cost){x,last[y],0},last[y]=tot;
}
int DFS(int x,int y)
{
	if (x==t) return y;
	int u=0,p;
	for (int i=cur[x];i;i=e[i].nex)
	{
		cur[x]=i;
		if (e[i].flow>0 && d[e[i].to]+1==d[x])
		{
			p=DFS(e[i].to,min(e[i].flow,y-u));
			u+=p,e[i].flow-=p,e[i^1].flow+=p;
			if (u==y) return u;
		}
	}
	cur[x]=last[x];
	if (!(--co[d[x]])) d[s]=num;
	++co[++d[x]];
	return u;
}
int main()
{
	cin>>n>>m>>c;
	for (int i=1;i<=m;i++) cin>>x>>y,bz[x+1][y+1]=1;
	s=n*n+1,t=s+1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			for (int k=0;k<4;k++)
			{
				x=i+fx[k][0],y=j+fx[k][1];
				if (!x || x>n || !y || y>n) continue;
				add(get(i,j),get(x,y),1);
			}
			if (bz[i][j]) add(s,get(i,j),1<<30);
			add(get(i,j),t,c);
		}
	num=t;
	co[0]=num;
	ans=-m*c;
	for (;d[s]<num;) ans+=DFS(s,1<<30);
	cout<<ans<<endl;
	return 0;
}