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;
}