1305. [CQOI2009]跳舞【最大流+二分】

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

HINT

N<=50 K<=30

这个题思路很妙啊……第一次做到在网络流中使用二分的题目
其实一开始想到用二分限制的，不过并没有深入思考下去
而是写了一个别人几行就能实现我却用网络流实现的贪心
正解是拆点加二分。
因为答案满足单调性，若可以跳x首曲子，则x-1首肯定也是可以的
建图？
将每个男生和女生拆成两个点：Yes和No

超级源点连接男生的Yes，超级汇点连接女生的Yes
容量设置为二分的x。若跑出来最大流是x*n，就说明满流了
满流即为可以满足x首曲子

对于互相喜欢的，我们在男女的两个Yes点间连边
不喜欢的，我们就在男女的两个No点间连边
那么如何限制k呢？
每个男Yes连自己的No，容量为k
每个女No连自己Yes，容量为k
这样就可以保证k了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #define MAXM (100000+10)
  7 #define MAXN (10000+10)
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     int Flow;
 13     int next;
 14     int to;
 15 }edge[MAXM*2];
 16 int Depth[MAXN],q[MAXN];
 17 int head[MAXN],num_edge;
 18 int n,m,k,s,e,d,INF;
 19 int a[1010][1010];
 20 char ch[1010];
 21 
 22 void add(int u,int v,int l)
 23 {
 24     edge[++num_edge].to=v;
 25     edge[num_edge].Flow=l;
 26     edge[num_edge].next=head[u];
 27     head[u]=num_edge;
 28 }
 29 
 30 bool Bfs(int s,int e)
 31 {
 32     int Head=0,Tail=1;
 33     memset(Depth,0,sizeof(Depth));
 34     Depth[s]=1;
 35     q[1]=s;
 36     while (Head<Tail)
 37     {
 38         ++Head;
 39         int x=q[Head];
 40         for (int i=head[x];i!=0;i=edge[i].next)
 41             if (!Depth[edge[i].to] && edge[i].Flow>0)
 42             {
 43                 Depth[edge[i].to]=Depth[x]+1;
 44                 q[++Tail]=edge[i].to;
 45             }
 46     }
 47     if (Depth[e]>0) return true;
 48     return false;
 49 }
 50 
 51 int Dfs(int x,int low)
 52 {
 53     int Min,f=0;
 54     if (x==e || low==0)
 55         return low;
 56     for (int i=head[x];i!=0;i=edge[i].next)
 57         if (edge[i].Flow>0 && Depth[edge[i].to]==Depth[x]+1 && (Min=Dfs(edge[i].to , min(low,edge[i].Flow) )))
 58         {
 59             edge[i].Flow-=Min;
 60             edge[((i-1)^1)+1].Flow+=Min;
 61             f+=Min;
 62             low-=Min;
 63         }
 64     return f;
 65 }
 66 
 67 int Dinic(int s,int e)
 68 {
 69     int Ans=0;
 70     while (Bfs(s,e))
 71             Ans+=Dfs(s,0x7fffffff);
 72     return Ans;
 73 }
 74 
 75 void Addline(int x)
 76 {
 77     memset(head,0,sizeof(head));
 78     memset(edge,0,sizeof(edge));
 79     num_edge=0;
 80     for (int i=1;i<=n;++i)
 81     {
 82         add(0,i+520,x);
 83         add(i+520,0,0);//超级源点 
 84         
 85         add(i+n+520,999,x);//超级汇点 
 86         add(999,i+n+520,0);
 87         
 88         add(i+520,i+250,k);
 89         add(i+250,i+520,0);
 90         
 91         add(i+n+250,i+n+520,k);
 92         add(i+n+520,i+n+250,0); 
 93     }
 94     for (int i=1;i<=n;++i)
 95     {
 96         for (int j=1;j<=n;++j)
 97             if (a[i][j]==1)
 98             {
 99                 add(i+520,j+n+520,1);
100                 add(j+n+520,i+520,0);
101             }
102             else
103             {
104                 add(i+250,j+n+250,1);
105                 add(j+n+250,i+250,0);
106             }
107     }
108 }
109 
110 int main()
111 {
112     s=0,e=999;
113     memset(&INF,0x7f,sizeof(INF));
114     scanf("%d%d",&n,&k);
115     for (int i=1;i<=n;++i)
116     {
117         scanf("%s",ch);
118         for (int j=1;j<=n;++j)
119             a[i][j]=(ch[j-1]=='Y');
120     }
121     int l=0,r=n*n;
122     while (l<r)
123     {
124         int mid=(l+r+1)/2;
125         Addline(mid);
126         int Max=Dinic(0,999);
127         if (Max==mid*n)
128             l=mid;
129         else
130             r=mid-1;
131     }
132     printf("%d",l);
133 }