过了样例,全WA,求助
查看原帖
过了样例,全WA,求助
366470
hc_awa楼主2022/6/28 10:30
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+7,M=5e6+7;

struct Edge {
	int nxt,to;
	int w;
}edge[M<<1];

int head[M],cur[N],tot=1;
int dep[N];
bool inque[N];

int ans;
int n,m,s,t,cnt;

inline void AddEdge(int u,int v,int w) {
	edge[++tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
	head[u]=tot;
	
	edge[++tot].nxt=head[v];
	edge[tot].to=u;
	edge[tot].w=w;
	head[v]=tot;
}

inline bool bfs() {
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v;i;i=edge[i].nxt) {
			cur[u]=head[u];
			v=edge[i].to;
			if(!dep[v] && edge[i].w) {
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t];
}

inline int dfs(int u,int flow) {
	if(u==t)
		return flow;
	int outflow=0;
	for(int i=cur[u],v,w;i && flow;i=edge[i].nxt) {
		cur[u]=i;
		v=edge[i].to,w=edge[i].w;
		if(w && dep[v]==dep[u]+1) {
			int res=dfs(v,min(flow,w));
			edge[i].w-=res;
			edge[i^1].w+=res;
			flow-=res;
			outflow+=res;
		}
	}
	if(!outflow)
		dep[u]=0;
	return outflow;
}

inline int Dinic() {
	int res=0;
	while(bfs())
		res+=dfs(s,inf);
	return res;
}

inline int GetId(int x,int y) {
	return (x-1)*m+y;
}

signed main() {
	scanf("%d%d",&n,&m);
	s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1,cnt=n*m;
	for(int i=1,x;i<=n;++i)
		for(int j=1;j<=m;++j) {
		scanf("%d",&x);
		ans+=x;
		AddEdge(s,GetId(i,j),x);
	}
	for(int i=1,x;i<=n;++i)
		for(int j=1;j<=m;++j) {
			scanf("%d",&x);
			ans+=x;
			AddEdge(GetId(i,j),t,x);
		}
	for(int i=1,x;i<n;++i)
		for(int j=1;j<=m;++j) {
			scanf("%d",&x);
			ans+=x;
			AddEdge(s,++cnt,x);
			AddEdge(cnt,GetId(i,j),inf);
			AddEdge(cnt,GetId(i+1,j),inf);
		}
	for(int i=1,x;i<n;++i)
		for(int j=1;j<=m;++j) {
		scanf("%d",&x);
		ans+=x;
		AddEdge(++cnt,t,x);
		AddEdge(GetId(i,j),cnt,inf);
		AddEdge(GetId(i+1,j),cnt,inf);
	}
	for(int i=1,x;i<=n;++i)
		for(int j=1;j<m;++j) {
		scanf("%d",&x);
		ans+=x;
		AddEdge(s,++cnt,x);
		AddEdge(cnt,GetId(i,j),inf);
		AddEdge(cnt,GetId(i,j+1),inf);
	}
	for(int i=1,x;i<=n;++i)
		for(int j=1;j<m;++j) {
		scanf("%d",&x);
		ans+=x;
		AddEdge(++cnt,t,x);
		AddEdge(GetId(i,j),cnt,inf);
		AddEdge(GetId(i,j+1),cnt,inf);
	}
	printf("%d",ans-Dinic());
    return 0;
}

2022/6/28 10:30
加载中...