9
20
2013
0

【BZOJ2150】部落战争【网络流】

由于只能向下走,这样路线就不可能达成一个环,而且又鉴于每个点只能到达一遍,每一次的代价只存在于重设出发点,于是很容易的就想到了最小路径覆盖,赤果果的网络流。把每个节点拆成两个,i入和i出。如果i可以到达j,那么就连一条i出到j入的边,再由源向每一个出连一条边,由入向汇连一条边。上述边的流量都为1。答案就是总的点数减最大流。当然这道题也可以用匈牙利算法做。

program p03;
    type
        bian=record
            next,point,f:longint;
        end;
    var
        b:array[0..5000000] of bian;
        p,dst,s:array[0..500000] of longint;
        pd:array[0..500000] of boolean;
        bo:array[1..600,1..600] of boolean;
        tot,len,i,j,n,m,r,c:longint;
        ch:char;
    procedure getchar(var ch:char);
        begin
            read(ch);
            while (ch<>'.') and (ch<>'x')do
                read(ch);
        end;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function change(k1,k2:longint):longint;
        var
            i,j,k,num:longint;
        begin
            if (k1=n*m*2+1) or (k2=0) then exit(k2);
            num:=0;
            i:=p[k1];
            while i<>-1 do begin
                j:=b[i].point;
                if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
                    k:=change(j,min(k2,b[i].f));
                    k2:=k2-k; num:=num+k;
                    dec(b[i].f,k); inc(b[i xor 1].f,k);
                    if k2=0 then break;
                end;
                i:=b[i].next;
            end;
            if num=0 then dst[k1]:=-1;
            exit(num);
        end;
    function bfs:boolean;
        var
            i,j,head,now:longint;
        begin
            fillchar(dst,sizeof(dst),-1);
            fillchar(pd,sizeof(pd),false);
            head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
            while head>now do begin
                inc(now);
                i:=p[s[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (pd[j]=false) and (b[i].f>0) then begin
                        dst[j]:=dst[s[now]]+1;
                        pd[j]:=true;
                        if j=n*m*2+1 then exit(true);
                        inc(head);
                        s[head]:=j;
                    end;
                    i:=b[i].next;
                end;
            end;
            exit(pd[n*m*2+1]);
        end;
    procedure ade(k1,k2,k3:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].f:=k3;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3:longint);
        begin
            ade(k1,k2,k3);
            ade(k2,k1,0);
        end;
    function dinic:longint;
        var
            num:longint;
        begin
            num:=0;
            while bfs=true do
                num:=num+change(0,maxlongint);
            exit(num);
        end;
    begin
        readln(n,m,r,c);
        fillchar(p,sizeof(p),-1);
        fillchar(b,sizeof(b),0);
        len:=-1;
        for i:=1 to n do
            for j:=1 to m do begin
                getchar(ch);
                if ch='.' then bo[i,j]:=true else bo[i,j]:=false;
            end;
        for i:=1 to n do
            for j:=1 to m do begin
                if (i+c<=n) and (j+r<=m) and (bo[i,j]=true) and (bo[i+c,j+r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j+r+n*m,1);
                if (i+r<=n) and (j+c<=m) and (bo[i,j]=true) and (bo[i+r,j+c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j+c+n*m,1);
                if (i+c<=n) and (j-r>0) and (bo[i,j]=true) and (bo[i+c,j-r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j-r+n*m,1);
                if (i+r<=n) and (j-c>0) and (bo[i,j]=true) and (bo[i+r,j-c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j-c+n*m,1);
            end;
        tot:=0;
        for i:=1 to n do
            for j:=1 to m do
                if bo[i,j]=true then begin
                    inc(tot);
                    add(0,i*m-m+j,1);
                    add(i*m-m+j+n*m,n*m*2+1,1);
                end;
        writeln(tot-dinic);
    end.       
Category: 最大流 | Tags: | Read Count: 1334

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com