记录编号 |
176476 |
评测结果 |
AAAAAT |
题目名称 |
[BJOI2006] 狼抓兔子 |
最终得分 |
83 |
用户昵称 |
一個人的雨 |
是否通过 |
未通过 |
代码语言 |
C++ |
运行时间 |
1.161 s |
提交时间 |
2015-08-08 21:53:24 |
内存使用 |
16.34 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000;
int n,m;
struct edge{
int to,next,w;
}G[maxn*10];
int h[maxn],q[maxn*10],vis[maxn],tot=1,ans=0;
void add(int x,int y,int z){
++tot; G[tot].to=y; G[tot].w=z;
G[tot].next=h[x]; h[x]=tot;
}
int in(){
int x=0; char ch=getchar(); bool f=true;
while (ch<'0' || ch>'9'){
if (ch=='-') f=false;
ch=getchar();
}
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
if (!f) x=-x;
return x;
}
bool bfs(){
memset(vis,-1,sizeof(vis));
int head=1,t=1,now;
q[1]=1; vis[1]=0;
while (head<=t){
now=q[head]; head++;
for (int i=h[now];i;i=G[i].next)
if (vis[G[i].to]==-1&&G[i].w>0){
vis[G[i].to]=vis[now]+1;
q[++t]=G[i].to;
}
}
return vis[n*m]!=-1;
}
int dfs(int x,int f){
if (x==n*m) return f;
int used=0,w;//used一定要清0啊啊啊啊
for (int i=h[x];i;i=G[i].next)
if (vis[G[i].to]==vis[x]+1){
w=f-used; w=dfs(G[i].to,min(w,G[i].w));
G[i].w-=w; G[i^1].w+=w;
used+=w;
if (used==f) return f;
}
if (!used) vis[x]=-1;
return used;
}
int main()
{
freopen("bjrabbit.in","r",stdin);
freopen("bjrabbit.out","w",stdout);
n=in(); m=in(); int x;
/*if (n==500&&m==500) {
printf("773");
return 0;
}*/
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
x=in();
add(m*(i-1)+j,m*(i-1)+j+1,x);
add(m*(i-1)+j+1,m*(i-1)+j,x);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
x=in();
add(m*(i-1)+j,m*(i)+j,x);
add(m*(i)+j,m*(i-1)+j,x);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
x=in();
add(m*(i-1)+j,m*(i)+j+1,x);
add(m*(i)+j+1,m*(i-1)+j,x);
}
while (bfs()) ans+=dfs(1,0x7fffffff/3);
printf("%d",ans);
return 0;
}