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

3

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
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            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
          
           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 else103 {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