刚学网络流的萌新求助
查看原帖
刚学网络流的萌新求助
200044
JS_TZ_ZHR楼主2021/4/23 22:29

这个哪里写错了啊...好久都调不出来

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,u,v,dis[400005],head[400005],cnt,ans,Sum,Now,dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0};
int now[400005],a[1005][1005],b[1005][1005],c[1005][1005],d[1005][1005];
char check[1005][1005];
struct node{
    int to,dis,nxt;
}e[10000005];
bool dinic(){
    queue<int>q;
    q.push(s);
    for(int i=s;i<=t;i++)dis[i]=1e9;
    dis[s]=0;
    now[s]=head[s];
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(!e[i].dis||dis[y]!=1e9)continue;
            dis[y]=dis[x]+1;
            now[y]=head[y];
            if(y==t)return 1;
            q.push(y);
        }
    }
    return 0;
}
inline void add(int u,int v,int w){
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v,e[cnt].dis=w;
    e[++cnt].nxt=head[v];
    head[v]=cnt;
    e[cnt].to=u,e[cnt].dis=0;
}
int dfs(int x,int sum){
    if(x==t)return sum;
    int res=0,num;
    for(int i=now[x];sum&&i;i=e[i].nxt){
        now[x]=i;
        int y=e[i].to;
        if(!e[i].dis||(dis[y]!=dis[x]+1))continue;
        num=dfs(y,min(sum,e[i].dis));
        if(!num)dis[y]=1e9;
        e[i].dis-=num;
        e[i^1].dis+=num;
        res+=num;
        sum-=num;
    }
    return res;
}
int main(){
    cin>>n>>m;
    Now=t=n*m+1; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			add(s,i*m-m+j,a[i][j]);
			Sum+=a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>b[i][j];
			add(i*m-m+j,t,b[i][j]);
			Sum+=b[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			Now++;
			add(s,Now,c[i][j]);
			add(Now,i*m-m+j,1e9);
			Sum+=c[i][j];
			for(int k=0;k<=4;k++){
				int nx=i+dx[k],ny=j+dy[k];
				if(nx<1||ny<1||nx>n||ny>m)continue;
				add(Now,nx*m-m+ny,1e9);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>d[i][j];
			Now++;
			add(Now,t,d[i][j]);
			add(i*m-m+j,Now,1e9);
			Sum+=d[i][j];
			for(int k=0;k<=4;k++){
				int nx=i+dx[k],ny=j+dy[k];
				if(nx<1||ny<1||nx>n||ny>m)continue;
				add(nx*m-m+ny,Now,1e9);
			}
		}
	}
	while(dinic())ans+=dfs(s,1e9);
	cout<<Sum-ans<<endl;
}
2021/4/23 22:29
加载中...