題干：

題目描述

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

輸入輸出格式

輸入格式：

?

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

第二行包含一個正整數(shù)M1，表示書和練習(xí)冊可能的對應(yīng)關(guān)系個數(shù)。

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

第M1+3行包含一個正整數(shù)M2，表述書和答案可能的對應(yīng)關(guān)系個數(shù)。

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：?復(fù)制

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：?復(fù)制

2

說明

樣例說明：

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

M1=5，表示書和練習(xí)冊共有5個可能的對應(yīng)關(guān)系，分別為：書4和練習(xí)冊3、書2和練習(xí)冊2、書5和練習(xí)冊2、書5和練習(xí)冊1以及書5和練習(xí)冊3。

M2=5，表示數(shù)和答案共有5個可能的對應(yīng)關(guān)系，分別為：書1和答案3、書3和答案1、書2和答案2、書3和答案3以及書4和答案3。

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

數(shù)據(jù)規(guī)模：

對于數(shù)據(jù)點(diǎn)1, 2, 3，M1，M2<= 20

對于數(shù)據(jù)點(diǎn)4~10，M1，M2 <= 20000

?

題目大意：

HansBug 眼前有?n_1?本書，n_2??本練習(xí)冊，n_3??本答案。已知一個完整的書冊均應(yīng)該包含且僅包含一本書、一本練習(xí)冊、一本答案。現(xiàn)在 HansBug 只知道?個可能的書和練習(xí)冊的對應(yīng)關(guān)系，個可能的書和答案的對應(yīng)關(guān)系。HansBug 想知道在這樣的情況下，最多可能同時組合成多少個完整的書冊。

數(shù)據(jù)范圍：??

解題報(bào)告：

? ?普通建圖是 練習(xí)冊 -> 書本 -> 答案。但是有一個問題：

這種情況相當(dāng)于書本被使用了兩次，所以需要拆點(diǎn)，把書本拆成兩個點(diǎn)來控制“這本書最多只能選擇一次”這個條件（至多只能被選入一個完整的書冊，不能同時出現(xiàn)在兩本書冊中）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 5e4 + 5; int n1,n2,n3,m1,m2; int tot; const ll INF = 0x3f3f3f3f3f3f3f3f; struct Edge {int to,ne;ll w; } e[MAX*20]; int head[MAX]; int st,ed; ll dis[MAX],q[MAX];//一共多少個點(diǎn)跑bfs，dis數(shù)組和q數(shù)組就開多大。 void add(int u,int v,ll w) {e[++tot].to=v; e[tot].w=w; e[tot].ne=head[u]; head[u]=tot;e[++tot].to=u; e[tot].w=0; e[tot].ne=head[v]; head[v]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];if(cur == ed) return 1;front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } ll dfs(int cur,ll limit) {//limit為源點(diǎn)到這個點(diǎn)的路徑上的最小邊權(quán) if(limit==0||cur==ed) return limit;ll w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=dfs(e[i].to,min(limit,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;limit-=w;if(limit==0) break;}}if(!flow) dis[cur]=-1;return flow; } ll dinic() {ll ans = 0;while(bfs(st,ed)) ans+=dfs(st,INF);return ans; } int main() {cin>>n2>>n1>>n3;st=0;ed=n1+n2*2+n3+1;tot=1;ll sum = 0;for(int i = 0; i<=ed; i++) head[i] = -1;for(int i = 1; i<=n1; i++) add(st,i,1);for(int i = n1+1; i<=n1+n2*2; i+=2) add(i,i+1,1);for(int i = n1+2*n2+1; i<=n1+n2*2+n3; i++) add(i,ed,1);cin>>m1;for(int a,b,i = 1; i<=m1; i++) {scanf("%d%d",&a,&b);add(b,n1+2*(a-1)+1,1);}cin>>m2;for(int a,b,i = 1; i<=m2; i++) {scanf("%d%d",&a,&b);add(n1+2*a, n1+2*n2+b,1);}printf("%lld\n",dinic());return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【洛谷 - P1231 】教辅的组成（网络流最大流，拆点）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。