被卡T8个点求助
查看原帖
被卡T8个点求助
190926
Diwanul楼主2021/3/3 13:27

RT,其他的点都可以在200ms内通过,但有8个点T掉了,是被什么情况卡了吗?

#include<bits/stdc++.h>

//#define TJ
#define DB puts("debug")

using namespace std;

const int fx[5]={0,0,1,-1,0},fy[5]={1,-1,0,0,0};
const int INF=0x3f3f3f3f;

struct edge{
	int to,nex,c; 
}e[2000010];

int n,m,ans;
int head[50010],te=1;
int d[50010],cur[50010];

void Add(int a,int b,int c){
	e[++te].c=c;
	e[te].nex=head[a];
	e[te].to=b;
	head[a]=te;
}

int Id(int x,int y,int z){
	return x*m+y+2+z*n*m;
}

bool Pd(int x,int y){
	return x<n&&x>=0&&y<m&&y>=0;
}

bool Bfs(){
	memset(d,-1,sizeof d);
	queue<int> q;
	d[1]=0,cur[1]=head[1];
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=e[i].nex){
			int v=e[i].to;
			if(!~d[v]&&e[i].c){
				q.push(v);
				d[v]=d[u]+1;
				cur[v]=head[v];
				if(!v)return 1;
			}
		}
	}
	return 0;
}

int Dfs(int u,int limit){
	if(!u)return limit;
	int res=0;
	for(register int i=cur[u];i;i=e[i].nex){
		cur[u]=i;
		int v=e[i].to;
		if(d[v]==d[u]+1&&e[i].c){
			int f=Dfs(v,min(e[i].c,limit-res));
			if(!f)d[v]=-1;
			e[i].c-=f,res+=f,e[i^1].c+=f;
		}
	}
	return res;
}

int Dinic(){
	int res=0,ls=0;
	while(Bfs())
//		while((ls=))
			res+=Dfs(1,INF);
	return res;
}

int main(){
	#ifdef TJ
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for(register int i=0;i<n;i++)
		for(register int j=0;j<m;j++){
			int x;
			scanf("%d",&x);
			ans+=x;
			Add(1,Id(i,j,0),x);
			Add(Id(i,j,0),1,0);
		}
	for(register int i=0;i<n;i++)
		for(register int j=0;j<m;j++){
			int x;
			scanf("%d",&x);
			ans+=x;
			Add(0,Id(i,j,0),0);
			Add(Id(i,j,0),0,x);
		}
	for(register int i=0;i<n;i++)
		for(register int j=0;j<m;j++){
			int x;
			scanf("%d",&x);
			ans+=x;
			Add(1,Id(i,j,1),x);
			Add(Id(i,j,1),1,0);
			for(register int k=0;k<5;k++){
				int nx=i+fx[k],ny=j+fy[k];
				if(Pd(nx,ny)){
					Add(Id(i,j,1),Id(nx,ny,0),INF);
					Add(Id(nx,ny,0),Id(i,j,1),0);
				}
			}
		}
	for(register int i=0;i<n;i++)
		for(register int j=0;j<m;j++){
			int x;
			scanf("%d",&x);
			ans+=x;
			Add(0,Id(i,j,2),0);
			Add(Id(i,j,2),0,x);
			for(register int k=0;k<5;k++){
				int nx=i+fx[k],ny=j+fy[k];
				if(Pd(nx,ny)){
					Add(Id(i,j,2),Id(nx,ny,0),0);
					Add(Id(nx,ny,0),Id(i,j,2),INF);
				}
			}
		}
	printf("%d\n",ans-Dinic());
	return 0;
}
2021/3/3 13:27
加载中...