本文共 1433 字，大约阅读时间需要 4 分钟。

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Input

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数，即舞曲数目的最大值。

Sample Input

3 0

YYY

YYY

YYY

Sample Output

3

N<=50 K<=30

前言

这题一开始看错题了QAQ。。然后想错的题还被帅爷爷秒了。。

题解

一开始不知道二分答案。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N=55*4;const int MAX=1<<30;int n,k;struct qq{  int x,y,z,last;}s[N*N*2];int num,last[N];int st,ed;void init (int x,int y,int z){    num++;    s[num].x=x;s[num].y=y;s[num].z=z;    s[num].last=last[x];    last[x]=num;    swap(x,y);z=0;    num++;    s[num].x=x;s[num].y=y;s[num].z=z;    s[num].last=last[x];    last[x]=num;}char ss[55][55];int shen;int h[N];bool Bt (){    memset(h,-1,sizeof(h));h[st]=1;    queue
        
          q; q.push(st); while (!q.empty()) { int x=q.front();q.pop(); for (int u=last[x];u!=-1;u=s[u].last) { int y=s[u].y; if (s[u].z>0&&h[y]==-1) { h[y]=h[x]+1; q.push(y); } } } return h[ed]!=-1;}int mymin (int x,int y){ return x
         
          0&&h[y]==h[x]+1&&s1
          
           >1; if (check(mid)) {l=mid+1;ans=mid;} else r=mid-1; } printf("%d\n",ans); return 0;}