40分,蜜汁WA。
求各位大佬找错QAQ
丑陋的代码:
// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
inline int read()
{
int n=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9')
{
n=n*10+ch-'0';
ch=getchar();
}
return n;
}
const int MAX=0x7fffffff;
int dis[1001000];
int n,m,s,t;
int head[600100],net[600100],to[600100],cap[600100];
int cnt=1;
void add(int x,int y,int c)
{
to[++cnt]=y;
cap[cnt]=c;
net[cnt]=head[x];
head[x]=cnt;
to[++cnt]=x;
cap[cnt]=0;
net[cnt]=head[y];
head[y]=cnt;
}
int BFS()
{
memset(dis,0,sizeof(dis));
dis[s]=1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=head[v];i;i=net[i])
{
if(dis[to[i]]==0&&cap[i]>0)
{
dis[to[i]]=dis[v]+1;
q.push(to[i]);
}
}
}
if(dis[t]>0) return 1;
return 0;
}
int find(int x,int low)
{
int a=0;
if(x==t)return low;
int sum=0;
for(int i=head[x];i;i=net[i])
{
if(dis[to[i]]==dis[x]+1&&cap[i]!=0&&(a=find(to[i],min(low,cap[i]))))
{
cap[i]-=a;
cap[i^1]+=a;
low-=a;
sum+=a;
if(low==0)
break;
}
}
return sum;
}
int ans=0,tans=0;
int get(int x,int y)
{
return (x-1)*m+y;
}
bool a[210][210];
int map[40100];
int way[2]={0,-1};
signed main()
{
cin>>n>>m;
s=0,t=2*n*m+1;
int tot=0;
int inf=0x7f;
way[0]=-m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
int num,a,b;
cin>>num;
a=get(i,j),b=a+n*m;
if(!num)
{
add(s,a,inf);
add(a,b,inf);
}
if(i==1||j==1||i==n||j==m)
{
add(b,t,inf);
}
if(num>0)
{
add(a,b,num);
}
for(int k=0; k<2; k++)
{
int newn=a+way[k];
if(newn>0&&newn<=n*m&&map[newn]!=-1&&num!=-1&&(!(k==1&&i==1)))
{
add(b,newn,inf);
add(newn+n*m,a,inf);
}
}
map[a]=num;
}
}
while(BFS())
{
while(tans=find(s,0x7fffffff)) ans+=tans;
}
cout<<ans;
return 0;
}