P1231 教辅的组成

求三重匹配最大匹配数。
\(N\leq 10^5\)，\(M_1\), \(M_2 \leq 20000\)。

---

首先要承认，这一题属于P3254的延申，可以先复习一下P3254的题解。

然而这一题又和P3254不太一样 （不就是从两条边匹配变成三条边吗） 那就错了！

看上面这张图，如果用最大流来跑，最后答案会是2条，但 \(N_1=1\) ，是错解。思考对策，发现问题出在中间的 \(P_1\) ，显然被重复算了。那么把中间的 \(P_1\) 用拆点拆成2个，中间连一条流量为1的边就能解决问题。

#include<bits/stdc++.h>
using namespace std;int n1,n2,n3,s,t;
int m1,m2,head[300005],ecnt=1,ans;
int dep[300005];
queue<int> q;
struct edge{int to,nxt,w;
}e[1000005];void adde(int u,int v,int w){e[++ecnt].nxt=head[u];e[ecnt].to=v;e[ecnt].w=w;head[u]=ecnt;
}bool Bfs(){memset(dep,0,sizeof(dep));dep[s]=1;while(q.size())q.pop();q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(e[i].w && !dep[v]){q.push(v);dep[v]=dep[u]+1;}}}return dep[t];
}int Dfs(int u,int in){if(u==t)return in;int out=0;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(e[i].w && dep[u]+1==dep[v]){int k=Dfs(v,min(in,e[i].w));in-=k;out+=k;e[i].w-=k;e[i^1].w+=k;}}if(out==0)dep[u]=0;return out;
}int main(){scanf("%d %d %d",&n1,&n2,&n3);s=0,t=n1+n2+n3+1;for(int i=1;i<=n2;++i){adde(s,n1+i,1);adde(n1+i,s,0);}scanf("%d",&m1);for(int i=1;i<=m1;++i){int ui,vi;scanf("%d %d",&ui,&vi);vi=vi+n1;adde(vi,ui,1);adde(ui,vi,0);}for(int i=1;i<=n1;++i){adde(i,t+i,1);adde(t+i,i,0);}scanf("%d",&m2);for(int i=1;i<=m2;++i){int ui,vi;scanf("%d %d",&ui,&vi);ui=t+ui;vi=n1+n2+vi;adde(ui,vi,1);adde(vi,ui,0);}for(int i=1;i<=n3;++i){adde(n1+n2+i,t,1);adde(t,n1+n2+i,0);}while(Bfs())ans+=Dfs(s,1000000000);printf("%d",ans);return 0;
}