- 1
- var head, gap, dis: array[0..10000] of longint;
- 2 vet,
- next,
- len,
- fan: array[1..200000] of longint;
- 3 num: array[1..50, 1..4] of longint;
- 4 a: array[1..50, 1..50] of char;
- 5 n,
- m,
- i,
- l,
- r,
- mid,
- last,
- s,
- source,
- src,
- tot,
- k1,
- j: longint;
- 6 ch: string;
- 7 8 procedure add(a, b, c: longint);
- 9 begin 10 inc(tot);
- 11 next[tot] : =head[a];
- 12 vet[tot] : =b;
- 13 len[tot] : =c;
- 14 head[a] : =tot;
- 15 inc(tot);
- 16 next[tot] : =head[b];
- 17 vet[tot] : =a;
- 18 len[tot] : =0;
- 19 head[b] : =tot;
- 20 end;
- 21 22
- function min(x, y: longint) : longint;
- 23 begin 24
- if xthen exit(x);
- 25 exit(y);
- 26 end;
- 27 28
- function dfs(u, aug: longint) : longint;
- 29
- var e, v, t, val, flow: longint;
- 30 begin 31
- if u = src then exit(aug);
- 32 e: =head[u];
- val: =s - 1;
- flow: =0;
- 33
- while e < >0 do 34 begin 35 v: =vet[e];
- 36
- if len[e] > 0 then 37 begin 38
- if dis[u] = dis[v] + 1 then 39 begin 40 t: =dfs(v, min(len[e], aug - flow));
- 41 len[e] : =len[e] - t;
- 42 len[fan[e]] : =len[fan[e]] + t;
- 43 flow: =flow + t;
- 44
- if dis[source] >= s then exit(flow);
- 45
- if aug = flow then
- break;
- 46 end;
- 47 val: =min(val, dis[v]);
- 48 end;
- 49 e: =next[e];
- 50 end;
- 51
- if flow = 0 then 52 begin 53 dec(gap[dis[u]]);
- 54
- if gap[dis[u]] = 0 then dis[source] : =s;
- 55 dis[u] : =val + 1;
- 56 inc(gap[dis[u]]);
- 57 end;
- 58 exit(flow);
- 59 end;
- 60 61
- function maxflow: longint;
- 62
- var ans: longint;
- 63 begin 64 fillchar(gap, sizeof(gap), 0);
- 65 fillchar(dis, sizeof(dis), 0);
- 66 gap[0] : =s;
- ans: =0;
- 67
- while dis[source] do ans: =ans + dfs(source, maxlongint);
- 68 exit(ans);
- 69 end;
- 70 71 procedure build;
- 72
- var i, j: longint;
- 73 begin 74 fillchar(head, sizeof(head), 0);
- 75 tot: =0;
- 76
- for i: =1 to n do 77 begin 78 add(num[i, 1], num[i, 2], k1);
- 79 add(num[i, 3], num[i, 4], k1);
- 80 end;
- 81
- for i: =1 to n do 82 begin 83 add(source, num[i, 1], mid);
- 84 add(num[i, 4], src, mid);
- 85 end;
- 86
- for i: =1 to n do 87
- for j: =1 to n do 88
- if a[i, j] = 'Y'then add(num[i, 1], num[j, 4], 1) 89
- else add(num[i, 2], num[j, 3], 1);
- 90 end;
- 91 92 begin 93 assign(input, 'bzoj1305. in ');
- reset(input);
- 94 assign(output, 'bzoj1305.out');
- rewrite(output);
- 95 readln(n, k1);
- 96
- for i: =1 to n do 97 begin 98 readln(ch);
- 99
- for j: =1 to n do a[i, j] : =ch[j];
- 100 end;
- 101
- for i: =1 to 200000 do 102
- if i mod 2 = 1 then fan[i] : =i + 1 103
- else fan[i] : =i - 1;
- 104
- for i: =1 to n do 105
- for j: =1 to 4 do 106 begin 107 inc(s);
- num[i, j] : =s;
- 108 end;
- 109 source: =s + 1;
- src: =s + 2;
- s: =s + 2;
- 110 l: =0;
- r: =n;
- last: =0;
- 111
- while l <= r do 112 begin 113 mid: =(l + r) >> 1;
- 114 build;
- 115
- if maxflow >= mid * n then begin last: =mid;
- l: =mid + 1;
- end 116
- else r: =mid - 1;
- 117 end;
- 118 writeln(last);
- 119 close(input);
- 120 close(output);
- 121 end.
来源: