求助,dinic被卡
查看原帖
求助,dinic被卡
363495
我爱杨帆楼主2021/2/5 15:16
#include<bits/stdc++.h>
#define re register
#define inf (1<<30)
const int sz=40001<<1;
using namespace std;
int read()
{
	char c=getchar();
	int r=0,f=1;
	while((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if(c=='-') {
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar();
	}
	return f*r;
}
struct node
{
	int to,nxt,c;
}e[480010];
int tot=1,head[30100],now[30100],dep[30100];
void add_edge(int x,int y,int z)
{
	e[++tot]=(node){y,head[x],z};head[x]=tot;
	e[++tot]=(node){x,head[y],0};head[y]=tot;
}
bool bfs(int s,int t)
{
	memset(dep,0,sizeof(dep));
	queue<int >q;
	dep[s]=1;now[s]=head[s];
	q.push(s);
	while(q.size())
	{
		int top=q.front();q.pop();
		for(int i=head[top];i;i=e[i].nxt)
			if(!dep[e[i].to]&&e[i].c)
			{
				q.push(e[i].to);
				now[e[i].to]=head[e[i].to];
				dep[e[i].to]=dep[top]+1;
				if(e[i].to==t) return 1;
			}
	}
	return 0;
}
int dfs(int x,int flow,int t)
{
	if(x==t) return flow;
	int rest=flow;
	for(int i=now[x];i;i=e[i].nxt)
	{
		now[x]=i;
		if(e[i].c&&dep[e[i].to]==dep[x]+1)
		{
			int k=dfs(e[i].to,min(rest,e[i].c),t);
			if(!k) dep[e[i].to]=0;
			e[i].c-=k;
			e[i^1].c+=k;
			rest-=k;
		}
	}
	return flow-rest;
}
int dinic(int s,int t)
{
	int maxflow=0,flow=0;
	while(bfs(s,t))
		while(flow=dfs(s,inf,t)) maxflow+=flow;
	return maxflow;
}
int n,m,art[105][105],science[105][105],same_art[105][105],same_science[105][105],sum;
int id(int x,int y)
{
	return (x-1)*m+y;
}
int sum1=0;
signed main()
{
	n=read(),m=read();
	int s=0,t=n*m*3+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			art[i][j]=read();
			sum1+=art[i][j];
			sum+=art[i][j];
			add_edge(s,id(i,j),art[i][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			science[i][j]=read();
			sum+=science[i][j];
			add_edge(id(i,j),t,science[i][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			same_art[i][j]=read();
			sum1+=same_art[i][j];
			sum+=same_art[i][j];
			add_edge(s,n*m+id(i,j),same_art[i][j]);
			add_edge(n*m+id(i,j),id(i,j),inf);
			if(i!=1) add_edge(n*m+id(i,j),id(i-1,j),inf);
			if(i!=n) add_edge(n*m+id(i,j),id(i+1,j),inf);
			if(j!=1) add_edge(n*m+id(i,j),id(i,j-1),inf);
			if(j!=m) add_edge(n*m+id(i,j),id(i,j+1),inf);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			same_science[i][j]=read();
			sum+=same_science[i][j];
			int x=n*m*2+id(i,j);
			add_edge(x,t,same_science[i][j]);
			add_edge(id(i,j),x,inf);
			if(i!=1) add_edge(id(i-1,j),x,inf);
			if(i!=n) add_edge(id(i+1,j),x,inf);
			if(j!=1) add_edge(id(i,j-1),x,inf);
			if(j!=m) add_edge(id(i,j+1),x,inf);
		}
	printf("%d\n",sum-dinic(s,t));
}

2021/2/5 15:16
加载中...