[CQOI2009]dance跳舞

Time Limit:10000MS Memory Limit:165536K
Total Submit:35 Accepted:19
Case Time Limit:1000MS

Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

N<=50
K<=30

Source
网络流建模真是越来越得心应手了(*^__^*) 。。这道题目很显然是要最优转判定的，比如判定能不能有T轮，怎么转呢，对每个男生建立3个定点表示全体，得到喜欢的，得到不喜欢的，那么源向全体连一条容量为T的边，全体向喜欢的连无穷大的边，全体向不喜欢的连容量为k的bian，然后女生也类似分为3个跟汇连，然后男生用喜欢节点向喜欢的女生的喜欢节点，用不喜欢节点向不喜欢的女生的不喜欢节点连容量为1连边。。就OK了。。
Code：

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=300+20;struct Edge{ int t,c; Edge(int _t,int _c,Edge* _next): t(_t),next(_next),c(_c){} Edge*next,*op;}*E[maxn]={0};int n,vs,vt;int h[maxn],vh[maxn],v;void InsEdge(int s,int t,int c){ //cout<<s<<" "<<t<<" "<<c<<endl; E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,0,E[t]); E[s]->op=E[t];E[t]->op=E[s];}const int All=0,Like=1,DontLike=2,inf=1<<20;inline int Boy(int x,int type){return x*3+type;}inline int Girl(int x,int type){return (n+x)*3+type;}void Init(){ int k;char x; scanf("%d %dn",&n,&k); v=n*6+2;vs=v-1;vt=v-2; rep(i,n)rep(j,n) { scanf("%cn",&x); int t=x==’Y’?Like:DontLike; InsEdge(Boy(i,t),Girl(j,t),1); } rep(i,n) { InsEdge(vs,Boy(i,All),0); InsEdge(Boy(i,All),Boy(i,Like),inf); InsEdge(Boy(i,All),Boy(i,DontLike),k); InsEdge(Girl(i,All),vt,0); InsEdge(Girl(i,Like),Girl(i,All),inf); InsEdge(Girl(i,DontLike),Girl(i,All),k); }}int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}int CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}void Work(){ int Flow=0; for(int i=1;;i++) { for(Edge*e=E[vs];e;e=e->next)e->c++; for(Edge*e=E[vt];e;e=e->next)e->op->c++; Flow+=CalFlow(); if(Flow!=i*n) { cout<<i-1<<endl; break; } }}int main(){ //freopen("in","r",stdin); Init(); Work();}33 0YYYYYYYYY