教輔的組成（網絡流果題 洛谷P1231）

題目描述

蒟蒻HansBug在一本語文書里面發現了一本答案，然而他卻明明記得這書應該還包含一份練習題。然而出現在他眼前的書多得數不勝數，其中有書，有答案，有練習冊。已知一個完整的書冊均應該包含且僅包含一本書、一本練習冊和一份答案，然而現在全都亂做了一團。許多書上面的字跡都已經模糊了，然而HansBug還是可以大致判斷這是一本書還是練習冊或答案，并且能夠大致知道一本書和答案以及一本書和練習冊的對應關系（即僅僅知道某書和某答案、某書和某練習冊有可能相對應，除此以外的均不可能對應）。既然如此，HansBug想知道在這樣的情況下，最多可能同時組合成多少個完整的書冊。

輸入輸出格式

輸入格式：

第一行包含三個正整數N1、N2、N3，分別表示書的個數、練習冊的個數和答案的個數。

第二行包含一個正整數M1，表示書和練習冊可能的對應關系個數。

接下來M1行每行包含兩個正整數x、y，表示第x本書和第y本練習冊可能對應。（1<=x<=N1，1<=y<=N2）

第M1+3行包含一個正整數M2，表述書和答案可能的對應關系個數。

接下來M2行每行包含兩個正整數x、y，表示第x本書和第y本答案可能對應。（1<=x<=N1，1<=y<=N3）

輸出格式：

輸出包含一個正整數，表示最多可能組成完整書冊的數目。

輸入輸出樣例

輸入樣例#1：

5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3

輸出樣例#1：

2

說明

樣例說明：

如題，N1=5，N2=3，N3=4，表示書有5本、練習冊有3本、答案有4本。

M1=5，表示書和練習冊共有5個可能的對應關系，分別為：書4和練習冊3、書2和練習冊2、書5和練習冊2、書5和練習冊1以及書5和練習冊3。

M2=5，表示數和答案共有5個可能的對應關系，分別為：書1和答案3、書3和答案1、書2和答案2、書3和答案3以及書4和答案3。

所以，以上情況的話最多可以同時配成兩個書冊，分別為：書2+練習冊2+答案2、書4+練習冊3+答案3。

數據規模：

對于數據點1, 2, 3，M1，M2<= 20

對于數據點4~10，M1，M2 <= 20000

題解：將書本拆點，練習冊連向書本1，書本2連向答案，再建立超級源點和超級匯點，跑一邊最大流即可，敲這題是為了打模板的。

#include<algorithm>
#include<fstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;int n1,n2,n3,m1,m2,x,y,cur;//n1是書，n2是練習冊，n3是答案，m1書冊，m2書答案 
int head[50050],lev[50050],q[50050];
struct tedge
{int to,nex,val;
}e[200010];void Add(int u,int v,int val)
{cur++;e[cur].to = v;e[cur].nex = head[u];e[cur].val = val;head[u] = cur;cur++;e[cur].to = u;e[cur].nex = head[v];e[cur].val = 0;head[v] = cur;
}int bfs(int S,int T)
{int h=1,t=1;for (int i=0; i<=2*n1+n2+n3+1+1; i++)lev[i] = 0;q[h] = S;  lev[S] = 1;while (h<=t){int u=q[h];for (int i=head[u]; i!=-1; i=e[i].nex){int v=e[i].to;if (lev[v]==0&&e[i].val>0){lev[v] = lev[u]+1;t++;  q[t]=v;}}h++;}return (max(lev[T],0));
}int dfs(int u,int T,int f)
{if (u==T||f==0) return f;int ret=0,d;for (int i=head[u]; i!=-1; i=e[i].nex){int v=e[i].to;if (lev[v]>lev[u]&&e[i].val>0){d=dfs(v,T,min(f,e[i].val));ret+=d;f-=d;e[i].val-=d;if (i%2==0) e[i-1].val+=d;else e[i+1].val+=d;if (f==0) break;}}return ret;
}void Dinic()
{int maxflow=0;for (;bfs(1,2*n1+n2+n3+1+1);)maxflow+=dfs(1,2*n1+n2+n3+1+1,1e9);printf("%d\n",maxflow);
}int main()
{freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%d%d%d",&n1,&n2,&n3);for (int i=0; i<=2*n1+n2+n3+1+1; i++)head[i] = -1;scanf("%d",&m1);for (int i=1; i<=m1; i++){int x,y;scanf("%d%d",&x,&y);Add(2*n1+y+1,x+1,1);}scanf("%d",&m2);for (int i=1; i<=m2; i++){int x,y;scanf("%d%d",&x,&y);Add(x+n1+1,2*n1+n2+y+1,1);}for (int i=1; i<=n1; i++)Add(i+1,i+n1+1,1);for (int i=1; i<=n2; i++)Add(1,2*n1+i+1,1);for (int i=1; i<=n3; i++)Add(2*n1+n2+i+1,2*n1+n2+n3+1+1,1);Dinic();return 0;
}

?