广州网站建设建航科技公司/seo标题优化的方法

https://www.luogu.org/problemnew/show/P1231
听说这题也可以用匹配来做？
网络流入门题。一份书册由一本书、一本练习册和一本答案组成，给出书与练习册以及书与答案的对应关系，求最多能组成多少份书册。
将书、题、答案的n1,n2,n3三组节点间建图，n2连源点，n3连汇点，容量设为1，跑一遍最大流。
注意如果不将书拆点，则一本书可以重复使用；将n1本书拆成两个连一条边，就能保证书中流过的流量也是1了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MX = 10001;
const int MXN = 1000001;
const int INF = 0x3f3f3f3f;
struct data{int u,v,nxt,flow;
}g[MXN];
int n1,n2,n3,m1,m2,u,v,ans;
int head[MXN],tot,s,t,level[6*MX],Q[MXN];
void addEdge(int u,int v,int val) {g[tot]=data{u,v,head[u],val};head[u]=tot++;g[tot]=data{v,u,head[v],0};head[v]=tot++;
}
bool bfs(int s,int t) {memset(level,0,sizeof(level));int l=-1,r=0;Q[r]=s;level[s]=1;while (l<r) {int u=Q[++l];if (u==t) return true;for (int i=head[u];i!=-1;i=g[i].nxt) {int v=g[i].v,flow=g[i].flow;if (level[v]==0&&flow!=0) {Q[++r]=v;level[v]=level[u]+1;}}}return false;
}
int dfs(int u,int maxFlow,int t) {if (u==t) return maxFlow;int res=0;for (int i=head[u];i!=-1&&res<maxFlow;i=g[i].nxt) {int v=g[i].v,flow=min(g[i].flow,maxFlow-res);if (level[v]==level[u]+1&&flow!=0) {flow=dfs(v,flow,t);g[i].flow-=flow;g[i^1].flow+=flow;res+=flow;}}if (res==0) level[u]=MXN;return res;
}
int main() {scanf("%d%d%d",&n1,&n2,&n3);memset(head,-1,sizeof(head));scanf("%d",&m1);while (m1--) {scanf("%d%d",&u,&v);addEdge(v,u+n2,1);}scanf("%d",&m2);while (m2--) {scanf("%d%d",&u,&v);addEdge(n2+n1+u,n2+n1+n1+v,1);}s=0,t=n1+n1+n2+n3+1;for (int i=1;i<=n1;++i)addEdge(i+n2,i+n2+n1,1);for (int i=1;i<=n2;++i)addEdge(s,i,1);for (int i=1;i<=n3;++i)addEdge(i+n2+n1+n1,t,1);while (bfs(s,t)) ans+=dfs(s,INF,t);printf("%d\n",ans);return 0;
}

//Version2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MX = 10001;
const int MXN = 1000001;
const int INF = 0x3f3f3f3f;
struct data{int u,v,nxt,flow;
}g[MXN];
int n1,n2,n3,m1,m2,u,v,ans;
int head[MXN],tot,s,t,level[6*MX],Q[MXN];
void addEdge(int u,int v,int val) {g[tot]=data{u,v,head[u],val};head[u]=tot++;g[tot]=data{v,u,head[v],0};head[v]=tot++;
}
bool bfs(int s,int t) {memset(level,0,sizeof(level));int l=-1,r=0;Q[r]=s;level[s]=1;while (l<r) {int u=Q[++l];if (u==t) return true;for (int i=head[u];i!=-1;i=g[i].nxt) {int v=g[i].v,flow=g[i].flow;if (level[v]==0&&flow!=0) {Q[++r]=v;level[v]=level[u]+1;}}}return false;
}
int dfs(int u,int maxFlow,int t) {if (u==t) return maxFlow;int res=0;for (int i=head[u];i!=-1&&res<maxFlow;i=g[i].nxt) {int v=g[i].v,flow=min(g[i].flow,maxFlow-res);if (level[v]==level[u]+1&&flow!=0) {flow=dfs(v,flow,t);g[i].flow-=flow;g[i^1].flow+=flow;res+=flow;}}if (res==0) level[u]=MXN;return res;
}
void dinic() {    while(bfs(s,t)) ans+=dfs(s,INF,t);    printf("%d\n",ans);
}
int main() {scanf("%d%d%d",&n1,&n2,&n3);memset(head,-1,sizeof(head));scanf("%d",&m1);while (m1--) {scanf("%d%d",&u,&v);addEdge(v,u+n1,1);}scanf("%d",&m2);while (m2--) {scanf("%d%d",&u,&v);addEdge(n2+n1+u,n2+n1+n1+v,1);}s=0,t=n1+n1+n2+n3+1;for (int i=1;i<=n1;++i)addEdge(i+n2,i+n2+n1,1);for (int i=1;i<=n2;++i)addEdge(s,i,1);for (int i=1;i<=n3;++i)addEdge(i+n2+n1+n1,t,1);    dinic();return 0;
}