- 1
- var dis: array[0..410] of longint;
- 2 flow: array[0..410, 0..410] of longint;
- 3 q: array[0..10000] of longint;
- 4 head,
- tail: longint;
- 5 n,
- m,
- x,
- p,
- z: longint;
- 6 i,
- j: longint;
- 7 ans: int64;
- 8 procedure bfs; //bfs 分层图
- 9
- var i: longint;
- 10 now: longint;
- 11 begin 12
- for i: =0 to p do 13 dis[i] : =-1;
- 14 dis[0] : =0;
- 15 head: =1;
- 16 tail: =1;
- 17 q[1] : =0;
- 18
- while head <= tail do 19 begin 20 now: =q[head];
- 21
- for i: =0 to p do 22
- if (flow[now, i] > 0) and(dis[i] < 0) then 23 begin 24 inc(tail);
- 25 q[tail] : =i;
- 26 dis[i] : =dis[now] + 1;
- 27 end;
- 28 inc(head);
- 29 end;
- 30 end;
- 31 32
- function dfs(x, mx: longint) : longint; //dfs最小流
- 33
- var k, i: longint;
- 34 begin 35
- if x = p then exit(mx);
- 36
- for i: =0 to p do 37
- if (flow[x, i] > 0) and(dis[i] = dis[x] + 1) then 38 begin 39
- if flow[x, i] > mx then k: =dfs(i, mx)
- else k: =dfs(i, flow[x, i]);
- 40 flow[x, i] : =flow[x, i] - k;
- 41 flow[i, x] : =flow[i, x] + k;
- 42
- if k > 0 then exit(k);
- 43 end;
- 44 exit(0);
- 45 end;
- 46 47 begin 48 read(n, m);
- 49 p: =n + m + 1; //p为总节点数 0 为源点s p 为汇点t
- 50
- for i: =1 to n do 51 begin 52 x: =1;
- 53
- while x < >0 do 54 begin 55 read(x);
- 56
- if x < >0 then flow[i, x + n] : =1; //建社团与人数的边,因为不能编号相同,所以 1~n 为社团 n+1~n+m 为人
- 57 end;
- 58 flow[0, i] : =1; //建s与社团的边
- 59 end;
- 60
- for i: =1 to m do 61 flow[n + i, p] : =1; //建人与t的边 i还是要加n 才是人的编号
- 62
- while true do //最大流
- 63 begin 64 bfs;
- 65
- if dis[p] < 0 then
- break;
- 66 repeat 67 z: =dfs(0, maxint);
- 68 ans: =ans + z;
- 69 until z > 0;
- 70 end;
- 71 writeln(ans);
- 72 end.
来源: