过不了样例求调
查看原帖
过不了样例求调
521283
wangif424楼主2024/7/16 20:31
#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
constexpr int N=300100,inf=1e17;
int n,m;
struct edge{
	int to,nxt,f;
}v[N<<5];
int len,fir[N];
void add(int x,int y,int f){
	++len;
	v[len].f=f;
	v[len].to=y;
	v[len].nxt=fir[x];
	fir[x]=len;
}
void ade(int x,int y,int f){
	add(x,y,f);
	add(y,x,0);
}
int s,t;
int d[N],fir2[N];
bool bfs(){
	queue<int> q;
	memset(d,-1,sizeof(d));
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		if(u==t)break;
		for(int&i=fir2[u];i;i=v[i].nxt){
			if(v[i].f>0&&d[v[i].to]==-1){
				d[v[i].to]=d[u]+1;
				q.push(v[i].to);
			}
		}		
	}
	return d[t]^(-1);
}
int dfs(int u,int val){
	if(u==t||!val)return val;
	int tmp=0;
	for(int&i=fir2[u];i;i=v[i].nxt){
		if(v[i].f<=0||d[v[i].to]!=d[u]+1)continue;
		int cut=dfs(v[i].to,min(val,v[i].f));
		v[i].f-=cut;
		v[i^1].f+=cut;
		tmp+=cut;
		val-=cut;
		if(!val)break;
	}
	if(!tmp)d[u]=-1;
	return tmp;
}
int sum,val;
int dinic(){
	int res=0;
	memcpy(fir2,fir,sizeof(fir2));
	while(bfs()){
		memcpy(fir2,fir,sizeof(fir2));
		res+=dfs(s,inf);
		memcpy(fir2,fir,sizeof(fir2));
	}
	return res;
}
int c(int x,int y){
	if(x<1||y<1||x>n||y>m)return 0;
	return 1;
}
int id(int x,int y,int tp){
	return (tp-1)*n*m+(x-1)*m+y;
}
int f[5][2]={{0,0},{0,1},{1,0},{-1,0},{0,-1}};
signed main(){
	R(n);R(m);
	s=id(n,m,3)+1,t=s+1;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		R(val);
		ade(s,id(i,j,1),val);
		sum+=val;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		R(val);
		ade(id(i,j,1),t,val);
		sum+=val;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		for(int k=0;k<5;k++){
			int x=i+f[k][0];
			int y=j+f[k][1];
			if(c(x,y))ade(id(i,j,2),id(x,y,1),inf);
		}
		R(val);
		ade(s,id(i,j,2),val);
		sum+=val;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		for(int k=0;k<5;k++){
			int x=i+f[k][0];
			int y=j+f[k][1];
			if(c(x,y))ade(id(x,y,1),id(i,j,3),inf);
		}
		R(val);
		ade(id(i,j,3),t,val);
		sum+=val;
	}
	write(sum-dinic());
    return 0;
}
2024/7/16 20:31
加载中...