关键词：
题目描述
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会”单向喜欢“）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
输入输出格式
输入格式：第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为‘Y‘当且仅当男孩i和女孩j相互喜欢。
输出格式：仅一个数，即舞曲数目的最大值。
输入输出样例
3 0
YYY
YYY
YYY
3
说明
N<=50 K<=30
Solution：
本题太毒，调了几天，终于又填完坑了～
像这种需要配对，而且数据还这么小的题目，一眼就容易想到网络最大流。
那么如果直接去跑最大流的话，显然不可行。
题意中说相同的两个人只能搭配一次，那么最多也就$50$次，很容易想到从大到小枚举天数然后跑最大流判断（我写了下枚举+最大流，事实证明是可以过的），但是，本题有很明显的单调性，即若前$i$天可以完整搭配，则答案一定在$[i,n]$之间，否则就在$[0,i-1]$之间。于是考虑二分答案，然后跑最大流$check$。
再来考虑最大流$check$是否可行。每个男生的点和女生的点相匹配，只有两种情况，要么不互相喜欢使用$1$次限制，要么互相喜欢不需要花费。
因为每人最多和不喜欢的匹配$k$次，于是我们将每个学生都拆成两个点，之间连边为$k$表示限制，假设男生$a$被拆为$a1,a2$（$a1$是$a$的全局，$a2$是与$a$不互相喜欢的分点），女生$b$被拆为$b1,b2$（类比男生的含义），每次二分的天数$x$，重新建图：$s\rightarrow a1$连容量为$x$（$s$为源点，该边表示每个人应该匹配$x$次），$a1\rightarrow a2$连容量为$k$（表示$a$最多和$k$个不喜欢的女生匹配），$b1,b2$类比男生连法（$b2\rightarrow b1\;\;b1\rightarrow t$）。每次若男生$a$和女生$b$不喜欢，连容量为$1$的边$a2\rightarrow b2$，若$a$和$b$互相喜欢，则应直接连容量为$1$的边$a1\rightarrow b1$。
然后每次跑完最大流后，看最大流是否等于$x*n$，便能判断是否成立。（最后需要注意的是二分的边界值：$l=0,r=n$，最少就是$1$次也无法搭配，最多就是$n$人互相搭配一次）
代码：
1 #include<bits/stdc++.h> 2 #define il inline 3 #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) 4 #define Min(a,b) ((a)>(b)?(b):(a)) 5 #define debug printf("%d %s\n",__LINE__,__FUNCTION__) 6 using namespace std; 7 const int N=100005,inf=23333333; 8 int s,t=5200,ans,dis[10005],n,k,to[N],net[N],h[10010],cnt=1,w[N]; 9 bool mp[55][55]; 10 11 il void add(int u,int v,int c)to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c; 12 13 il bool bfs() 14 queue<int>q; 15 memset(dis,-1,sizeof(dis)); 16 q.push(s),dis[s]=0; 17 while(!q.empty()) 18 int u=q.front();q.pop(); 19 for(int i=h[u];i;i=net[i]) 20 if(dis[to[i]]==-1&&w[i]>0)dis[to[i]]=dis[u]+1,q.push(to[i]); 21 22 return dis[t]!=-1; 23 24 25 il int dfs(int u,int op) 26 if(u==t)return op; 27 int flow=0,used=0; 28 for(int i=h[u];i;i=net[i]) 29 int v=to[i]; 30 if(dis[v]==dis[u]+1&&w[i]>0) 31 used=dfs(v,Min(w[i],op)); 32 if(!used)continue; 33 flow+=used,op-=used; 34 w[i]-=used,w[i^1]+=used; 35 if(!op)break; 36 37 38 if(!flow)dis[u]=-1; 39 return flow; 40 41 42 il bool check(int x) 43 memset(h,0,sizeof(h)); 44 cnt=1; 45 For(i,1,n) 46 add(s,i,x),add(i,s,0); 47 add(i,i+n,k),add(i+n,i,0); 48 add(i+n*3,t,x),add(t,i+n*3,0); 49 add(i+n*2,i+n*3,k),add(i+n*3,i+n*2,0); 50 51 For(i,1,n) For(j,1,n) 52 if(mp[i][j])add(i,j+3*n,1),add(j+3*n,i,0); 53 else add(i+n,j+2*n,1),add(j+2*n,i+n,0); 54 55 int tot=0; 56 while(bfs())tot+=dfs(s,inf); 57 if(tot==n*x)return 1; 58 return 0; 59 60 61 int main() 62 ios::sync_with_stdio(0); 63 cin>>n>>k; 64 char p; 65 For(i,1,n) For(j,1,n) 66 cin>>p; 67 if(p==‘Y‘)mp[i][j]=1; 68 if(n==1&&(p==‘Y‘||k>=1))cout<<1;return 0; 69 70 int mid,l=0,r=n; 71 while(l<=r) 72 mid=l+r>>1; 73 if(check(mid))l=mid+1,ans=mid; 74 else r=mid-1; 75 76 cout<<ans; 77 return 0; 78
[bzoj1305][cqoi2009]跳舞(网络流)(代码片段)
1305:[CQOI2009]dance跳舞TimeLimit:5Sec MemoryLimit:162MBSubmit:3944 Solved:1692[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳... 查看详情
cqoi2009跳舞(代码片段)
...量彼此会出现不相等的情况。所以我们现在需要确定一下跳舞 查看详情
1305:[cqoi2009]dance跳舞(代码片段)
TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 4169 Solved: 1804[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两... 查看详情
bzoj1305:[cqoi2009]dance跳舞（二分答案+网络流）(代码片段)
1305:[CQOI2009]dance跳舞题目：传送门 题解： 一眼网络流基础建模...然后就GG了 二分答案+拆点建边+最大流判断： 把男女生拆为男1，男2，女1，女2 1、男1和男2还有女1和女2之间连边，流量为约束条件k 2、st连... 查看详情
[cqoi2009]跳舞(代码片段)
...看就是网络流了之后想一想怎么搞发现题目的意思是使得跳舞最少的男生跳的舞最多很自然想到二分答案啊现在转化成了一个判定性问题，能否使得所有人都跳上(k)只舞由于喜欢和不喜欢的人放在一起并不好限制，于是只能拆点... 查看详情
bzoj1305:[cqoi2009]dance跳舞
题目链接bzoj1305:[CQOI2009]dance跳舞题解男,女生拆点A1A2，B1B2，拆成两点间分别连容量为K的边，限制与不喜欢的人跳舞的数量A1连接源点容量为x，B1连接汇点容量为x，x即为歌曲数目对与相互喜欢的男女直在A1，B1间接连容量为1的边... 查看详情
bzoj1305:[cqoi2009]dance跳舞
这题一眼过去网络流，关键是怎么流的问题。。然后回忆起了好久没用过的二分答案+网络流。解法很神奇，主要是构图问题，直接看代码应该看得懂吧（懒得写23333#include<cstdio>#include<iostream>#include<cstring>#include<cst... 查看详情
bzoj1305[cqoi2009]dance跳舞
1305:[CQOI2009]dance跳舞TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 2693 Solved: 1111[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。 查看详情
[cqoi2009]dance跳舞（isap写法）
https://daniu.luogu.org/problemnew/show/3153 #include<queue>#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;#defineN2501#defineM3001#defineinf2e9intn, 查看详情
bzoj1305:[cqoi2009]dance跳舞
...），给出一个字符矩阵代表男生女生之间的关系。他们要跳舞，跳舞的时候有歌，可以跳若干首歌，每一首歌他们只能选择之前的歌曲中没有选择过的异性舞伴，每个男生和女生最多只能和k个他们不喜欢的人跳舞，求出最多能... 查看详情
1305.[cqoi2009]跳舞最大流+二分
...单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？Input第一行包含两个整数n和k。以下 查看详情
bzoj1305[cqoi2009]dance跳舞
...ghtarrowB2_i,[k]$$G2_i ightarrowG1_i,[k]$表示至多跟k个不喜欢的人跳舞。如果$(i,j)$喜欢，那么$B1_i ightarrow 查看详情
[bzoj1305][cqoi2009]dance跳舞
...单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？n<=50,k<=30题解：很明显可以二分答案，然后... 查看详情
bzoj1305[cqoi2009]dance跳舞（二分+网络流）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1305 【题目大意】 一次舞会有n个男孩和n个女孩。 每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。 每个男孩都不会和同一个女孩跳两首（或更... 查看详情
bzoj千题计划130：bzoj1305:[cqoi2009]dance跳舞
http://www.lydsy.com/JudgeOnline/problem.php?id=1305 每个人拆为喜欢（yes）和不喜欢（no)两个点二分答案1、每两个人之间只能跳一次喜欢则男yesi向女yesj连流量为1的边不喜欢则 男noi向女noj连流量为1的边2、最多与k个不喜欢的人跳男y... 查看详情
[cqoi2009]叶子的染色(代码片段)
https://www.zybuluo.com/ysner/note/1307594题面戳我解析一开始脑抽了，状态转移时默认直接在子结点染色。。。其实这道题还是很简单的。设(dp[0/1/2][u])表示子树内的叶子结点还需要颜色(0/1)，或都不需要颜色。然后直接转移就对了。#incl... 查看详情
[cqoi2009]中位数(前缀和)(代码片段)
[CQOI2009]中位数题目描述给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。输入输出格式输入格式：第一行为两个正整数n和b，第二行为1~n的... 查看详情
p3154[cqoi2009]循环赛(代码片段)
传送门双倍经验题->这里//minamoto#include<bits/stdc++.h>#definellunsignedlonglong#defineRregister#definefp(i,a,b)for(Rinti=a,I=b+1;i<I;++i)#definefd(i,a,b)for(Rinti=a,I=b-1;i>I;--i)usingnamespaces 查看详情