1458: 士兵占领

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

数据范围

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

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

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

 1 const
 2     maxn=110;
 3 var
 4     map:array[0..maxn*2,0..maxn*2]of longint;
 5     dis,his,vh,pre:array[0..maxn*2]of longint;
 6     n,m,k,s,t,flow:longint;
 7 
 8 procedure init;
 9 var
10     i,j,x,y:longint;
11 begin
12     read(n,m,k);
13     s:=0;
14     t:=n+m+1;
15     for i:=1 to n do
16       begin
17         read(map[s,i]);
18         map[s,i]:=m-map[s,i];
19       end;
20     for i:=1 to m do
21       begin
22         read(map[i+n,t]);
23         map[i+n,t]:=n-map[i+n,t];
24       end;
25     for i:=1 to n do
26       for j:=1 to m do
27         map[i,j+n]:=1;
28     for i:=1 to k do
29       begin
30         read(x,y);
31         dec(map[x,y+n]);
32         dec(map[s,x]);
33         dec(map[y+n,t]);
34         if (map[s,x]<0) or (map[y+n,t]<0) then
35         begin
36           writeln('JIONG!');
37           halt;
38         end;
39       end;
40 end;
41 
42 procedure sap;
43 var
44     i,j,min,aug:longint;
45     flag:boolean;
46 begin
47     vh[0]:=t+1;
48     aug:=maxlongint;
49     i:=0;
50     while dis[i]<=t do
51       begin
52         his[i]:=aug;
53         flag:=false;
54         for j:=0 to t do
55           if (dis[j]+1=dis[i]) and (map[i,j]>0) then
56           begin
57             flag:=true;
58             if aug>map[i,j] then aug:=map[i,j];
59             pre[j]:=i;
60             i:=j;
61             if i=t then
62             begin
63               inc(flow,aug);
64               while i<>s do
65                 begin
66                   inc(map[i,pre[i]],aug);
67                   dec(map[pre[i],i],aug);
68                   i:=pre[i];
69                 end;
70               aug:=maxlongint;
71             end;
72             break;
73           end;
74         if flag then continue;
75         min:=t;
76         for j:=0 to t do
77           if (map[i,j]>0) and (dis[j]<min) then min:=dis[j];
78         dec(vh[dis[i]]);
79         if vh[dis[i]]=0 then break;
80         dis[i]:=min+1;
81         inc(vh[min+1]);
82         if i<>s then
83         begin
84           i:=pre[i];
85           aug:=his[i];
86         end;
87       end;
88     writeln(n*m-k-flow);
89 end;
90 
91 begin
92     init;
93     sap;
94 end.

View Code