# 38 条题解

• @ 2017-01-23 23:48:25

//bzoj1412 狼和羊的故事
#include<bits/stdc++.h>
#define inf 100000007
#define INF 100000007
#define N 200005
using namespace std;
struct Edge{
int u,v,f,next;
}G[2*N];
const int dx[5]={0,1,0,-1,0};
const int dy[5]={0,0,1,0,-1};
int a[105][105];
int n,m;
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
}
int level[2*N];
inline bool bfs(int s,int t){
memset(level,0,sizeof(level));
queue<int> q;
q.push(s);level[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
if(u==t)return 1;
int v=G[i].v,f=G[i].f;
if(level[v]==0&&f!=0){q.push(v);level[v]=level[u]+1;}
}
}
return 0;
}
int dfs(int u,int maxf,int t){
if(u==t)return maxf;
int rat=0;
int v=G[i].v,f=G[i].f;
if(level[v]==level[u]+1&&f){
int Min=min(f,maxf-rat);
f=dfs(v,Min,t);
G[i].f-=f;G[i^1].f+=f;rat+=f;
}
}
if(!rat)level[u]=inf;
return rat;
}
int main(){
int s=0,T=10001;int ans=0;int xx,yy;
for(int i=1;i<=n;i++)
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
for (int k=1;k<=4;k++){
xx=i+dx[k];
yy=j+dy[k];
if (xx<1||xx>n||yy<1||yy>m||a[i][j]==2) continue;
if (a[i][j]!=1||a[xx][yy]!=1){
}
}
while (bfs(s,T)) ans+=dfs(s,INF,T);
printf("%d",ans);
return 0;
}

• @ 2016-02-12 18:34:05
• @ 2013-10-10 14:12:06

拆点最大流
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 101
#define MAXV 10010

struct node {
node *next,*pair;
int t,f;
};

int gap[MAXV],h[MAXV];
int n,m;
int a[MAXN][MAXN],N[MAXN][MAXN];
int v=0;
int S,T;

void INSERT(int s,int t,int f){
node *p=new(node);
p->t=t;
p->f=f;
p=new(node);
p->t=s;
p->f=0;
}

int sap(int v,int flow){
if (v==T){
return flow;
}
int rec=0;
for (node *p=d[v];p;p=p->next){
if (p->f&&h[v]==h[p->t]+1){
int ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
d[v]=p;
if ((rec+=ret)==flow){
return flow;
}
}
}
if (!(--gap[h[v]])){
h[S]=T;
}
gap[++h[v]]++;
return rec;
}

int main(){
memset(gap,0,sizeof(gap));
memset(h,0,sizeof(h));
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
for (int j=0;j++<m;){
N[i][j]=++v;
scanf("%d",&a[i][j]);
}
}
S=++v;
T=++v;
for (int i=0;i++<n;){
for (int j=0;j++<m;){
if (i-1){
INSERT(N[i][j],N[i-1][j],1);
}
if (j-1){
INSERT(N[i][j],N[i][j-1],1);
}
if (i+1<=n){
INSERT(N[i][j],N[i+1][j],1);
}
if (j+1<=m){
INSERT(N[i][j],N[i][j+1],1);
}
switch (a[i][j]){
case 1:
INSERT(S,N[i][j],0x7fffffff);
break;
case 2:
INSERT(N[i][j],T,0x7fffffff);
break;
}

}
}
gap[0]=T;
for (int i=0;i++<T;){
}
int mincut=0;
while (h[S]<T){
mincut+=sap(S,0x7fffffff);
}
printf("%d\n",mincut);
return 0;
}

• @ 2010-04-10 10:41:55

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

太可惜了，一开始把m写成n，只有40

• @ 2010-04-05 22:11:05
• @ 2010-03-16 21:45:45

第100个Ac。。。

• @ 2010-03-15 21:28:22

Accepted 有效得分：100 有效耗时：0ms

第99个AC，纪念一下，膜拜zkw神牛！

zkw=重口味？

• @ 2010-03-14 21:13:17

第97人~~~~~

二做网络流

终于有点感觉了

……

加油

• @ 2010-03-11 18:33:04

最小割模型

• @ 2009-10-19 17:28:24

我彻底被这道题鄙视了！！！

• @ 2009-10-08 16:09:33

晕....交了三次

• @ 2009-10-03 16:58:57

第一次：编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

第二次：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

重写了一遍后，终于。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

....

sap很不错啊~

• @ 2009-09-10 22:39:05

编译通过...

• @ 2009-09-07 18:08:27

按照复杂度分析死超了。 dinic在实际效果中还不错。

• @ 2009-08-21 15:04:43

sap+gap+当前弧+puppy=ms

• @ 2009-08-15 13:50:38

Orz zlq巨牛！！！

• @ 2009-08-11 10:31:26

最小割最大流

program yzl;

const

dx:array [1..4] of integer=(-1,1,0,0);

dy:array [1..4] of integer=(0,0,1,-1);

oo=100000000;

var

n,i,j,k,p,q,t,m,ret:longint;

a:array [0..101,0..101] of longint;

num:array [0..101,0..101] of longint;

tot,ans,mint,s,sum:longint;

y:array [0..100001] of boolean;

queue:array [0..200001] of longint;

pre:array [0..100001] of longint;

dis:array [0..100001] of longint;

function oppsite(k:longint):longint;

begin

if odd(k) then exit(k+1)

else exit(k-1);

end;

begin

inc(sum);

arrive[sum]:=v;

flow[sum]:=w;

inc(sum);

arrive[sum]:=u;

flow[sum]:=0;

end;

procedure bfs;

var

flag:boolean;

begin

repeat

flag:=false;

tail:=1;

fillchar(y,sizeof(y),true);

y:=false;

queue[1]:=s;

repeat

while now0 do begin

if y[arrive[now]] and (flow[now]>0) then begin

pre[arrive[now]]:=now;

y[arrive[now]]:=false;

inc(tail);

queue[tail]:=arrive[now];

if arrive[now]=t then begin

flag:=true;

break;

end;

end;

now:=next[now];

end;

if flag then begin

inc(ans);

v:=t;

while vs do begin

dec(flow[pre[v]]);

inc(flow[oppsite(pre[v])]);

v:=arrive[oppsite(pre[v])];

end;

end;

until not flag;

end;

function extended_flow:boolean;

var

begin

fillchar(dis,sizeof(dis),0);

queue[1]:=s;

dis:=1;

ret:=t;

tail:=1;

repeat

while v0 do begin

if (flow[v]0)and(dis[arrive[v]]=0) then begin

dis[arrive[v]]:=dis+1;

inc(tail);

queue[tail]:=arrive[v];

end;

v:=next[v];

end;

if dis[t]0 then exit(true);

exit(false);

end;

procedure dinic(u:longint);

var

vv,v:longint;

begin

if ut then begin

while v0 do begin

if (flow[v]>0)and(dis[arrive[v]]=dis+1) then begin

pre[arrive[v]]:=v;

dinic(arrive[v]);

if dis>dis[ret] then exit;

ret:=t;

end;

v:=next[v];

end;

dis:=0;

end else begin

inc(ans);

vv:=t;

while vvs do begin

dec(flow[pre[vv]]);

inc(flow[oppsite(pre[vv])]);

if flow[pre[vv]]=0 then

ret:=arrive[oppsite(pre[vv])];

vv:=arrive[oppsite(pre[vv])];

end;

end;

end;

procedure _bfs;

var

flag:boolean;

begin

while extended_flow do

dinic(s);

end;

begin

s:=n*m+1;

t:=s+1;

sum:=0;

for i:=1 to n do begin

for j:=1 to m do begin

inc(tot);

num:=tot;

end;

end;

for i:=1 to n do

for j:=1 to m do begin

for k:=1 to 4 do begin

p:=i+dx[k];

q:=j+dy[k];

end;

end;

// bfs;

_bfs;

writeln(ans);

end.

• @ 2009-07-24 18:39:59

SAP 1A

• @ 2009-07-24 13:01:34

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

当我参加一试的时候,刚刚接触网络流,当时第二题就0。

当我参加二试的时候,还不精通网络流,当时第二题10。

现在,看看就是水题。。。

• @ 2009-07-18 17:37:48

dinic也可以啊

ID
1555

6

752

220

29%

1