DINIC 63PTS求调
查看原帖
DINIC 63PTS求调
643818
I_AK_CTS楼主2025/6/20 08:20
#include<bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
#define i64 int64_t
#define se second
#define fi first
using namespace std;
const int N=105,M=N*N*4,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct E
{
	int ne,to,c;
}e[M];
int n,m,a[N][N],h[M],ct,lv[N],sum,cu[M];
int get(int x,int y){return (x-1)*m+y;}
void add(int u,int v,int c)
{
	e[ct]={h[u],v,c},h[u]=ct++;
	e[ct]={h[v],u,0},h[v]=ct++;
}
bool bfs()
{
	memset(lv,-1,sizeof(lv));
	memcpy(cu,h,sizeof(h));
	queue<int> q;
	q.push(0),lv[0]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=h[x];~i;i=e[i].ne)
		{
			int v=e[i].to,c=e[i].c;
			if(c&&lv[v]==-1)
			{
				lv[v]=lv[x]+1;
				q.push(v);
			}
		}
	}
	return ~lv[n*m+1];
}
int dfs(int x,int F)
{
	if(x==n*m+1||!F) return F;
	int res=0;
	for(int i=cu[x];~i&&F;i=e[i].ne)
	{
		int v=e[i].to,c=e[i].c;
		if(lv[v]==lv[x]+1&&c)
		{
			int C=dfs(v,min(F,c));
			res+=C,F-=C,e[i].c-=C,e[i^1].c+=C;
		}
	}
	return res;
}
int dinic()
{
	int ans=0;
	while(bfs()) ans+=dfs(0,INF);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int x;cin>>x,sum+=x;
			if((i+j)&1)
			{
				add(0,get(i,j),x);
				for(int k=0;k<4;k++)
				{
					int xx=i+dx[k],yy=dy[k]+j;
					if(xx<1||xx>n||yy<1||yy>m) continue;
					add(get(i,j),get(xx,yy),INF);
				}
			}
			else add(get(i,j),n*m+1,x);
		}
	cout<<sum-dinic();
	return 0;
}
2025/6/20 08:20
加载中...