SWUNOJ 1861

二分答案,拆点做最大流
每个人拆成两个点,一个点用来连合作过的所有人,另一个点连没有合作过的所有人
源点向所有男生“合作过的点”引边,女生“合作过的点”向汇点引边,流量为当前的答案值即场次
男生“合作过的点”向“未合作过的点”引边,女生“未合作过的点”向“合作过的点”引边,流量为限制K
对于所给矩阵,若$Dij=Y$则i男向j女“合作过的点”引容量为1的边,反之在“未合作过的点”之间引边
最后得到最大流为场次乘以人数即存在可行解

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 205
#define maxm 200005
#define rever(x) (mem+((x-mem)^1))
struct edge
{
int s,t,v;
edge* next;
}mem[maxm*2],*head[maxn];
int cnt=-1;
void add_edge(int s,int t,int v)
{
mem[++cnt].s=s;mem[cnt].t=t;mem[cnt].v=v;mem[cnt].next=head[s];head[s]=mem+cnt;
mem[++cnt].s=t;mem[cnt].t=s;mem[cnt].v=0;mem[cnt].next=head[t];head[t]=mem+cnt;
}
int n,m;
int S,T;
int numbs[maxn];
int d[maxn];
edge* cur[maxn],*revpath[maxn];
void bfs()
{
queue<int> q;
while(!q.empty()) q.pop();
for (int i=0;i<=n;i++) d[i]=maxn-1;
d[T]=0;q.push(T);
while(!q.empty())
{
int u=q.front();
q.pop();
for (edge* it=head[u];it;it=it->next)
{
edge *now=rever(it);
if (now->v==0||d[now->s]<n) continue;
d[now->s]=d[u]+1;
q.push(now->s);
}
}
memset(numbs,0,sizeof(numbs));
for (int i=0;i<=n;i++) numbs[d[i]]++;
}
int isap()
{
int flow=0;
for (int i=0;i<=n;i++) cur[i]=head[i];
int u=S;
while(d[S]<n)
{
if (u==T)
{
int augflow=2147483647;
for (int i=S;i!=T;i=cur[i]->t)
augflow=min(augflow,cur[i]->v);
for (int i=S;i!=T;i=cur[i]->t)
{
cur[i]->v-=augflow;
rever(cur[i])->v+=augflow;
}
flow+=augflow;u=S;
}
edge *e;
for (e=cur[u];e;e=e->next)
if (e->v&&d[u]==(d[e->t]+1)) break;
if (e)
{
cur[u]=e;
revpath[e->t]=rever(e);
u=e->t;
}
else
{
numbs[d[u]]--;
if (numbs[d[u]]==0) break;
cur[u]=head[u];
int mindist=n;
for (edge* it=head[u];it;it=it->next)
if (it->v) mindist=min(mindist,d[it->t]);
d[u]=mindist+1;
numbs[d[u]]++;
if (u!=S) u=revpath[u]->t;
}
}
return flow;
}
int N,K;
char dat[60][60];
bool check(int now)
{
cnt=-1;memset(head,0,sizeof(head));
for (int i=1;i<=N;i++) {add_edge(S,i,now);add_edge(i+2*N,T,now);}
for (int i=1;i<=N;i++) {add_edge(i,i+N,K);add_edge(i+3*N,i+2*N,K);}
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
if (dat[i][j]=='Y') add_edge(i,j+2*N,1);
else add_edge(i+N,j+3*N,1);
bfs(); return isap()==N*now;
}
int main()
{
scanf("%d%d",&N,&K);
for (int i=1;i<=N;i++) scanf("%s",dat[i]+1);
S=0;T=4*N+1;n=T;
int L=0,R=50;
while(R-L>1)
{
int M=(L+R)>>1;
if (check(M)) L=M;
else R=M;
}
if (check(L)) printf("%d",L);
else printf("%d",R);
return 0;
}