1458: 士兵占领 - BZOJ

Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及士兵的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。
Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)
Sample Input

4 4 4

1 1 1 1

0 1 0 3

1 4

2 2

3 3

4 3

Sample Output

4

数据范围

M, N <= 100, 0 <= K <= M * N

 

 

 

看数据范围，应该可以用网络流吧，但是他要最小化，于是我们就机智地转换成先填满然后最大限度的拿掉士兵就行了

每一列建一个点，每一行建一个点，能拿掉的士兵就从对应的行向列连一条容量为1的边，行和列加上容量限制（就是最多可以拿掉多少）

const
    maxn=110;
var
    map:array[0..maxn*2,0..maxn*2]of longint;
    dis,his,vh,pre:array[0..maxn*2]of longint;
    n,m,k,s,t,flow:longint;

procedure init;
var
    i,j,x,y:longint;
begin
    read(n,m,k);
    s:=0;
    t:=n+m+1;
    for i:=1 to n do
      begin
        read(map[s,i]);
        map[s,i]:=m-map[s,i];
      end;
    for i:=1 to m do
      begin
        read(map[i+n,t]);
        map[i+n,t]:=n-map[i+n,t];
      end;
    for i:=1 to n do
      for j:=1 to m do
        map[i,j+n]:=1;
    for i:=1 to k do
      begin
        read(x,y);
        dec(map[x,y+n]);
        dec(map[s,x]);
        dec(map[y+n,t]);
        if (map[s,x]<0) or (map[y+n,t]<0) then
        begin
          writeln('JIONG!');
          halt;
        end;
      end;
end;

procedure sap;
var
    i,j,min,aug:longint;
    flag:boolean;
begin
    vh[0]:=t+1;
    aug:=maxlongint;
    i:=0;
    while dis[i]<=t do
      begin
        his[i]:=aug;
        flag:=false;
        for j:=0 to t do
          if (dis[j]+1=dis[i]) and (map[i,j]>0) then
          begin
            flag:=true;
            if aug>map[i,j] then aug:=map[i,j];
            pre[j]:=i;
            i:=j;
            if i=t then
            begin
              inc(flow,aug);
              while i<>s do
                begin
                  inc(map[i,pre[i]],aug);
                  dec(map[pre[i],i],aug);
                  i:=pre[i];
                end;
              aug:=maxlongint;
            end;
            break;
          end;
        if flag then continue;
        min:=t;
        for j:=0 to t do
          if (map[i,j]>0) and (dis[j]<min) then min:=dis[j];
        dec(vh[dis[i]]);
        if vh[dis[i]]=0 then break;
        dis[i]:=min+1;
        inc(vh[min+1]);
        if i<>s then
        begin
          i:=pre[i];
          aug:=his[i];
        end;
      end;
    writeln(n*m-k-flow);
end;

begin
    init;
    sap;
end.