题目大意:有三个集合 (P,Q,N),P 与 N 集合之间存在一些有向边,N 与 Q 集合之间存在一些有向边。在三个集合中每个点最多只能利用一次的前提下,求最多能利用多少N 集合中的点,使得 ((p,n,q)) 三个节点之间均有边相连。
题解:若只有两个集合,显然是二分图的最大匹配问题。对于三个集合来说,最麻烦的问题在于 N 集合中每个点只能被选一次,但是一个 N 集合中的节点却可能对应着多个P、Q 集合中的节点。保证 N 只能被选一次的方法是:将 N 集合中的点拆分成两个点,分别表示入点和出点,且连接入点和出点之间的边权为 1。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=410;
const int maxm=1e5+10;
int n,p,q,s,t,maxflow,d[maxn];
struct node{int nxt,to,w;}e[maxm<<1];
int tot=1,head[maxn];
inline void add_edge(int from,int to,int w){
e[++tot]=node{head[from],to,w},head[from]=tot;
e[++tot]=node{head[to],from,0},head[to]=tot;
}
bool bfs(){
queue<int> q;
memset(d,0,sizeof(d));
d[s]=1,q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(w&&!d[v]){
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dinic(int u,int flow){
if(u==t)return flow;
int rest=flow;
for(int i=head[u];i&&rest;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(w&&d[v]==d[u]+1){
int k=dinic(v,min(flow,w));
if(!k)d[v]=0;
e[i].w-=k,e[i^1].w+=k,rest-=k;
}
}
return flow-rest;
}
void read_and_parse(){
scanf("%d%d%d",&n,&p,&q);
s=0,t=2*n+p+q+1;
for(int i=1;i<=n;i++)add_edge(i,i+n,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++){
int x;scanf("%d",&x);
if(x)add_edge(j+2*n,i,1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=q;j++){
int x;scanf("%d",&x);
if(x)add_edge(i+n,2*n+p+j,1);
}
for(int i=2*n+1;i<=2*n+p;i++)add_edge(s,i,1);
for(int i=2*n+p+1;i<=2*n+p+q;i++)add_edge(i,t,1);
}
void solve(){
int now;
while(bfs())while(now=dinic(s,0x3f3f3f3f))maxflow+=now;
printf("%d
",maxflow);
}
int main(){
read_and_parse();
solve();
return 0;
}