38 条题解

  • 1
    @ 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 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;
    }

  • 0
    @ 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;
    };

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

  • 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

  • 0
    @ 2010-03-16 21:45:45

    第100个Ac。。。

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

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

    第99个AC,纪念一下,膜拜zkw神牛!

    zkw=重口味?

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

    第97人~~~~~

    二做网络流

    终于有点感觉了

    ……

    加油

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

    最小割模型

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

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

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

    晕....交了三次

  • 0
    @ 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很不错啊~

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

    编译通过...

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

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

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

    sap+gap+当前弧+puppy=ms

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

    Orz zlq巨牛!!!

  • 0
    @ 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;

    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.

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

    SAP 1A

  • 0
    @ 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。

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

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

    dinic也可以啊

信息

ID
1555
难度
6
分类
图结构 | 网络流 点击显示
标签
递交数
757
已通过
225
通过率
30%
被复制
2
上传者