//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 head[4*N],tot;
int a[105][105];
int n,m;
int read(){
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;
}
void addedge(int u,int v,int f){
G[tot].v=v;G[tot].u=u;G[tot].f=f;G[tot].next=head[u];head[u]=tot++;
G[tot].v=u;G[tot].u=v;G[tot].f=0;G[tot].next=head[v];head[v]=tot++;
}
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;
for(int i=head[u];i!=-1;i=G[i].next){
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;
for(int i=head[u];i!=-1&&rat<maxf;i=G[i].next){
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(){
memset(head,-1,sizeof(head));
int s=0,T=10001;int ans=0;int xx,yy;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)a[i][j]=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
if (a[i][j]==1) { addedge(0,(i-1)*m+j,INF);}
if (a[i][j]==2) { addedge((i-1)*m+j,T,INF);}
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){
addedge((i-1)*m+j,(xx-1)*m+yy,1);}
}
}
while (bfs(s,T)) ans+=dfs(s,INF,T);
printf("%d",ans);
return 0;
}

http://www.cnblogs.com/JSZX11556/p/4811641.html 网络流

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

using namespace std;

#define MAXN 101
#define MAXV 10010

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

node *head[MAXV],*d[MAXV];

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->next=head[s];
head[s]=p;
p=new(node);
p->t=s;
p->f=0;
p->next=head[t];
head[t]=p;
head[s]->pair=head[t];
head[t]->pair=head[s];
}

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]]++;
d[v]=head[v];
return rec;
}

int main(){
memset(head,0,sizeof(head));
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;){
d[i]=head[i];
}
int mincut=0;
while (h[S]<T){
mincut+=sap(S,0x7fffffff);
}
printf("%d\n",mincut);
return 0;
}

编译通过...

├ 测试数据 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

http://acm.hdu.edu.cn/showproblem.php?pid=3046

第100个Ac。。。

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

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

zkw=重口味？

第97人~~~~~

二做网络流

终于有点感觉了

……

加油

最小割模型

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

晕....交了三次

第一次：编译通过...

├ 测试数据 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很不错啊~

编译通过...

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

sap+gap+当前弧+puppy=ms

Orz zlq巨牛！！！

最小割最大流

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;

arrive,flow,next,road:array [0..100001] of 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;

procedure addedge(u,v,w:longint);

begin

inc(sum);

arrive[sum]:=v;

flow[sum]:=w;

next[sum]:=road;

road:=sum;

inc(sum);

arrive[sum]:=u;

flow[sum]:=0;

next[sum]:=road[v];

road[v]:=sum;

end;

procedure bfs;

var

head,tail,now,v:longint;

flag:boolean;

begin

repeat

flag:=false;

head:=0;

tail:=1;

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

y:=false;

queue[1]:=s;

repeat

inc(head);

k:=queue[head];

now:=road[k];

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;

until flag or (head>=tail);

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

head,tail,v,u:longint;

begin

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

queue[1]:=s;

dis:=1;

ret:=t;

head:=0;

tail:=1;

repeat

inc(head);

u:=queue[head];

v:=road;

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

until head>=tail;

exit(false);

end;

procedure dinic(u:longint);

var

vv,v:longint;

begin

if ut then begin

v:=road;

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

head,tail,now,v,u:longint;

flag:boolean;

begin

while extended_flow do

dinic(s);

end;

begin

readln(n,m);

s:=n*m+1;

t:=s+1;

sum:=0;

for i:=1 to n do begin

for j:=1 to m do begin

read(a);

inc(tot);

num:=tot;

end;

readln;

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

addedge(num,num[p,q],1);

end;

if a=1 then addedge(s,num,oo);

if a=2 then addedge(num,t,oo);

end;

// bfs;

_bfs;

writeln(ans);

end.

SAP 1A

编译通过...

├ 测试数据 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。

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

dinic也可以啊