Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？Input第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。Output仅一个数，即舞曲数目的最大值。Sample Input3 0YYYYYYYYYSample Output3HINTN<=50 K<=30
二分答案+最大流判定
把男和女每个点都拆成两个节点，一个处理喜欢的，一个处理不喜欢的，男的为i和i'，女的为j和j'
假设我们二分的答案为p
那么从s向所有的i连容量为p的边，从所有的j向t连容量为p的边
喜欢的男女对应的i向j连容量为1的边，不喜欢的男女对应的i向j连容量为1的边
所有的男的i向i'连容量为k的边，所有女的j'向j连容量为k的边
如果可行，那么最大流为p*n
上述算法的正确性基于以下定理：若二分图中，X部中点度数全为t，Y部中点度数全为t，那么该图定存在t个完全不同的完备匹配。用归纳法易证。
t=1时一定是对的，当t>1时，直接去掉一个匹配，就变成了t-1的问题了
现在我们就是要证明的是，t>0时一定存在一个匹配，当t=1时，有唯一的匹配，当t>1时，显然至少有一个匹配（我不知道怎么严格的证明......有的话留言给我吧，谢谢）
网上还看见有贪心的做法，我觉得不对，我也写了一个贪心的做法，WA了，估计是因为贪心不对，所以BZOJ加强了数据吧
我觉得贪心不对是因为这个
我们一开始给了无限大的流量（喜欢的为无限大，不喜欢的为k），然后取最小值，但是这样流量参差不齐，我们在减少那些大的流量时，可能会把这些小的流量变得更小（我自己瞎想的，勿喷）
1 const 2 maxn=55; 3 inf=10000; 4 var 5 map:array[0..maxn*4,0..maxn*4]of longint; 6 a:array[0..maxn,0..maxn]of char; 7 n,k,s,t,l,r,mid:longint; 8 9 procedure init; 10 var 11 i,j:longint; 12 begin 13 readln(n,k); 14 s:=0; 15 t:=4*n+1; 16 for i:=1 to n do 17 begin 18 for j:=1 to n do 19 read(a[i,j]); 20 readln; 21 end; 22 end; 23 24 var 25 his,dis,vh,pre:array[0..maxn*4]of longint; 26 min,aug,flow:longint; 27 flag:boolean; 28 29 function sap:boolean; 30 var 31 i,j:longint; 32 begin 33 fillchar(map,sizeof(map),0); 34 fillchar(dis,sizeof(dis),0); 35 fillchar(vh,sizeof(vh),0); 36 flow:=0; 37 for i:=1 to n do 38 for j:=1 to n do 39 if a[i,j]='Y' then map[2*i,2*j+2*n]:=1 40 else map[2*i-1,2*j+2*n-1]:=1; 41 for i:=1 to n do 42 begin 43 map[s,2*i]:=mid; 44 map[2*i+2*n,t]:=mid; 45 map[2*i,2*i-1]:=k; 46 map[2*i+2*n-1,2*i+2*n]:=k; 47 end; 48 vh[0]:=t+1; 49 i:=s; 50 aug:=inf; 51 while dis[i]<=t do 52 begin 53 his[i]:=aug; 54 flag:=false; 55 for j:=s to t do 56 if (map[i,j]>0) and (dis[i]=dis[j]+1) then 57 begin 58 pre[j]:=i; 59 flag:=true; 60 if aug>map[i,j] then aug:=map[i,j]; 61 i:=j; 62 if i=t then 63 begin 64 inc(flow,aug); 65 while i<>s do 66 begin 67 inc(map[i,pre[i]],aug); 68 dec(map[pre[i],i],aug); 69 i:=pre[i]; 70 end; 71 aug:=inf; 72 end; 73 break; 74 end; 75 if flag then continue; 76 min:=t; 77 for j:=s to t do 78 if (map[i,j]>0) and (min>dis[j]) then min:=dis[j]; 79 dec(vh[dis[i]]); 80 if vh[dis[i]]=0 then break; 81 dis[i]:=min+1; 82 inc(vh[dis[i]]); 83 if i<>s then 84 begin 85 i:=pre[i]; 86 aug:=his[i]; 87 end; 88 end; 89 exit(flow=mid*n); 90 end; 91 92 begin 93 init; 94 l:=0; 95 r:=n; 96 while l<>r do 97 begin 98 mid:=(l+r+1)>>1; 99 if sap then l:=mid100 else r:=mid-1;101 end;102 write(l);103 end.