看menci的博客点出二分的思路然后做出来，menci太强辣

原题：

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

N<=50 K<=30

 

看榜上的都是0MS，这是什么神奇的做法

先看menci的博客发现这道题，知道是网络流，想了一段时间无果，回menci的博客看了一眼，然后发现两个字

"二分"

然后思路就想出来了，二分答案，根据答案建图然后验证是否能跑到满流

具体建图方法就很简答了，相互喜欢的男女权值为1，每个男女要额外一个点来保证和不喜欢的人的限制，本来的点和额外的点中间权值为k，两个不喜欢的男女之间额外的点权值为1，源到男，女到汇权值为二分的答案

如果能跑到满流就说明答案和法

另外有一点需要注意就是二分的下线要从0开始，因为可能会无解

二分也是转换问题很关键的方式，以后想题还要尽量考虑一下

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int oo=168430090; 9 int rd(){ int z=0,mk=1; char ch=getchar();10 while(ch<'0'||ch>'9'){ if(ch=='-')mk=-1; ch=getchar();}11 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}12 return z*mk;13 }14 struct ddd{ int y,v,re;}; vector 
            
              e[210];15 inline void ist(int x,int y,int z){16 e[x].push_back((ddd){y,z,e[y].size()});17 e[y].push_back((ddd){x,0,e[x].size()-1});18 }19 int n,m; int s,t; int n2,n3,n4;20 char a[60][60];21 int lvl[210];22 int q[210],hd=0;23 void clear(){ for(int i=s;i<=t;++i) e[i].clear();}24 bool gtlvl(){25 memset(lvl,0,sizeof(lvl));26 q[hd=1]=s,lvl[s]=1;27 int x,sz;28 for(int k=1;k<=hd;++k){29 x=q[k],sz=e[x].size();30 for(int i=0;i
             
              >1; (chck(md)?l:r)=md;}66 return chck(r)?r:l;67 }68 int main(){ //freopen("ddd.in","r",stdin);69 cin>>n>>m; n2=n*2,n3=n*3,n4=n*4; s=0,t=n4+1;70 /*for(int i=1;i<=n;++i){71 scanf("%s",s+1);72 for(int j=1;j<=n;++j){73 if(s[j]=='Y') ist(i,j+3n,1);74 else ist(i+n,j+2n,1);75 }76 ist(i,i+n,k),ist(i+2n,i+3n,k);*/77 for(int i=1;i<=n;++i) scanf("%s",a[i]+1);78 cout<
              
               <