求助,只过了样例,WA0分
查看原帖
求助,只过了样例,WA0分
233815
zhjzhmh楼主2022/4/18 20:47
#include<bits/stdc++.h>
#define ma(i,j) ((i-1)*n+j)
using namespace std;
long long n,m,s,t,u,v,cnt,head[100010],dep[100010],cur[100010],a[100010],b[100010],x,y,z,ss,now;
struct node{int to,next,w;}edge[5000010];
void add(int u,int v,int w) {edge[cnt].to=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt++;}
void Add(int u,int v,int w) {add(u,v,w);add(v,u,0);}
bool bfs()
{
	memset(dep,0,sizeof(dep));dep[s]=1;queue<int> q;q.push(s);memcpy(cur,head,sizeof(head));
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(edge[i].w>0&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int flow)
{
	if(u==t) return flow;
	int fl=0;
	for(int i=cur[u];~i&&flow>0;i=edge[i].next)
	{
		int v=edge[i].to;cur[u]=i;
		if(edge[i].w>0&&dep[v]==dep[u]+1)
		{
			int c=dfs(v,min(flow,edge[i].w));
			edge[i].w-=c;edge[i^1].w+=c;flow-=c;fl+=c;
		}
	}
	if(!fl) dep[u]=0;
	return fl;
}
int dinic()
{
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,0x3f3f3f3f);
	return maxflow;
}
int main()
{
	cin>>n>>m;memset(head,-1,sizeof(head));s=0;t=m*n+1;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&a[ma(i,j)]),ss+=a[ma(i,j)];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&b[ma(i,j)]),ss+=b[ma(i,j)];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) Add(0,ma(i,j),a[ma(i,j)]),Add(ma(i,j),t,b[ma(i,j)]);now=t;
	for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) scanf("%lld",&a[ma(i,j)]),ss+=a[ma(i,j)];
	for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) scanf("%lld",&b[ma(i,j)]),ss+=b[ma(i,j)];
	for(int i=1;i<=n-1;i++)
	  for(int j=1;j<=m;j++)
	    Add(0,++now,a[ma(i,j)]),Add(now,ma(i,j),0x3f3f3f3f),Add(now,ma(i+1,j),0x3f3f3f3f),Add(++now,t,b[ma(i,j)]),Add(now,ma(i,j),0x3f3f3f3f),Add(now,ma(i+1,j),0x3f3f3f3f);
	for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++) scanf("%lld",&a[ma(i,j)]),ss+=a[ma(i,j)];
	for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++) scanf("%lld",&b[ma(i,j)]),ss+=b[ma(i,j)];
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m-1;j++)
	    Add(0,++now,a[ma(i,j)]),Add(now,ma(i,j),0x3f3f3f3f),Add(now,ma(i,j+1),0x3f3f3f3f),Add(++now,t,b[ma(i,j)]),Add(now,ma(i,j),0x3f3f3f3f),Add(now,ma(i,j+1),0x3f3f3f3f);
	cout<<ss-dinic();
	return 0;
} 

RT

2022/4/18 20:47
加载中...