[CQOI2009]跳舞

思路：
二分答案+最大流。
二分答案$m$，表示最多跳$m$轮。
将每个人拆成两个点$a_i$$b_i$，$a_i$表示与任何人跳舞，$b_i$表示与不喜欢的人跳舞。
对于第$i$个人，连一条从$a_i$到$b_i$的容量为$k$的边，表示与不同的不喜欢的人最多跳$k$次。
对于互相喜欢的男女$i$和$j$，连一条从$a_i$到$a_j$的容量为$1$的边，表示与同一个喜欢的人最多跳$1$次。
对于没有互相喜欢的男女$i$和$j$，连一条从$b_i$到$b_j$的容量为$1$的边，表示与同一个不喜欢的人最多跳$1$次。
建立超级源点$s$和超级汇点$t$。
对于每个男生$i$，连一条从$s$到$a_i$的容量为$m$的边，表示一个人跳$m$次舞。
对于每个女生$j$，连一条从$a_j$到$t$的容量为$m$的边，表示一个人跳$m$次舞。
每次二分时跑网络流，观察是否能够满流，若满流，则表示可以达到$m$轮。

  1 #include<queue>
  2 #include<vector>
  3 #include<cstring>
  4 #include<iostream>
  5 const int inf=0x7fffffff;
  6 const int N=51,E=5400,V=202;
  7 bool like[N][N];
  8 struct Edge {
  9     int from,to,remain;
 10 };
 11 Edge e[E];
 12 std::vector<int> g[V];
 13 int sz=0;
 14 inline void add_edge(const int u,const int v,const int w) {
 15     e[sz]=(Edge){u,v,w};
 16     g[u].push_back(sz);
 17     sz++;
 18 }
 19 int n,k,s,t;
 20 inline void init() {
 21     sz=0;
 22     for(int i=s;i<t;i++) g[i].clear();
 23 }
 24 inline void setGraph(const int m) {
 25     init();
 26     for(int i=1;i<=n;i++) {
 27         add_edge(s,i,m);
 28         add_edge(i,s,0);
 29     }
 30     for(int i=1;i<=n;i++) {
 31         add_edge(i,i+n,k);
 32         add_edge(i+n,i,0);
 33     }
 34     for(int i=1;i<=n;i++) {
 35         for(int j=1;j<=n;j++) {
 36             if(like[i][j]) {
 37                 add_edge(i,j+n*2,1);
 38                 add_edge(j+n*2,i,0);
 39             }
 40             else {
 41                 add_edge(i+n,j+n*3,1);
 42                 add_edge(j+n*3,i+n,0);
 43             }
 44         }
 45     }
 46     for(int i=1;i<=n;i++) {
 47         add_edge(i+n*3,i+n*2,k);
 48         add_edge(i+n*2,i+n*3,0);
 49     }
 50     for(int i=1;i<=n;i++) {
 51         add_edge(i+n*2,t,m);
 52         add_edge(t,i+n*2,m);
 53     }
 54 }
 55 int a[V],p[V];
 56 inline int Augment() {
 57     memset(a,0,sizeof a);
 58     a[s]=inf;
 59     std::queue<int> q;
 60     q.push(s);
 61     while(!q.empty()) {
 62         int x=q.front();
 63         q.pop();
 64         for(unsigned i=0;i<g[x].size();i++) {
 65             Edge &y=e[g[x][i]];
 66             if(!a[y.to]&&y.remain) {
 67                 a[y.to]=std::min(y.remain,a[x]);
 68                 p[y.to]=g[x][i];
 69                 q.push(y.to);
 70             }
 71         }
 72         if(a[t]) break;
 73     }
 74     return a[t];
 75 }
 76 inline int EdmondsKarp() {
 77     int maxflow=0;
 78     while(int flow=Augment()) {
 79         for(int i=t;i!=s;i=e[p[i]].from) {
 80             e[p[i]].remain-=flow;
 81             e[p[i]^1].remain+=flow;
 82         }
 83         maxflow+=flow;
 84     }
 85     return maxflow;
 86 }
 87 inline bool check(const int m) {
 88     setGraph(m);
 89     return EdmondsKarp()==m*n;
 90 }
 91 int main() {
 92     std::ios_base::sync_with_stdio(false);
 93     std::cin.tie(NULL);
 94     std::cin>>n>>k;
 95     s=0,t=n<<2|1;
 96     for(int i=1;i<=n;i++) {
 97         for(int j=1;j<=n;j++) {
 98             char ch;
 99             std::cin>>ch;
100             like[i][j]=ch=='Y';
101         }
102     }
103     int l=0,r=n;
104     while(l<=r) {
105         int mid=(l+r)>>1;
106         if(check(mid)) {
107             l=mid+1;
108         }
109         else {
110             r=mid-1;
111         }
112     }
113     std::cout<<l-1<<std::endl;
114     return 0;
115 }