（ 圖論專題 ）【 網絡最大流 】
推薦視訊：https://www.bilibili.com/video/av65039892?from=search&seid=1822150581423158194
推薦閱讀：https://blog.csdn.net/stevensonson/article/details/79177530
網絡流圖是一張隻有一個源點和彙點的有向圖，而最大流就是求源點到彙點間的最大水流量，下圖的問題就是一個最基本，經典的最大流問題
題目連結：https://www.luogu.org/problem/P3376
題目描述
如題，給出一個網絡圖，以及其源點和彙點，求出其網絡最大流。
輸入格式
第一行包含四個正整數N、M、S、T，分别表示點的個數、有向邊的個數、源點序号、彙點序号。
接下來M行每行包含三個正整數ui、vi、wi，表示第i條有向邊從ui出發，到達vi，邊權為wi（即該邊最大流量為wi）
輸出格式
一行，包含一個正整數，即為該網絡的最大流。
輸入樣例 #1
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
輸出樣例 #1
50
代碼：
/*
之前的模闆有些問題，現在更新了一下。
1.最終要的一個更新：在dfs中及時break。
當sum==flow就是，目前的流已經流滿了，直接break掉
2.目前弧優化
在bfs裡cur複制head數組， 在dfs裡用cur數組并且更新cur數組。
https://www.luogu.org/problem/P3386 這個題不優化就會T
*/
#include <bits/stdc++.h>
using namespace std;
struct node {
int to,f,nxt;
};
const int maxn = 2e6+10;
node e[maxn];
int n,m,s,t;
int head[maxn];
int cur[maxn];
int dep[maxn];
int cnt;
void addage( int u, int v, int f )
{
e[cnt].to = v;
e[cnt].f = f;
e[cnt].nxt = head[u];
head[u] = cnt++;
}
int bfs(int node)
{
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(cur)); // 複制head數組
dep[node] = 1;
queue <int> Q;
Q.push(node);
while ( !Q.empty() ) {
int x = Q.front();Q.pop();
for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
int y = e[i].to,f = e[i].f;
if ( !dep[y] && f ) {
dep[y] = dep[x] + 1;
Q.push(y);
}
}
}
return dep[t]; // return dep[t] ， 如果是0那麼說明沒有增廣路了，退出while
}
int dfs( int x, int flow ) // dfs找增廣路
{
if ( x==t ) {
return flow;
}
int sum = 0;
for ( int i=cur[x]; i!=-1; i=e[i].nxt ) {
cur[x] = i;
int y = e[i].to, f = e[i].f;
if ( f && dep[y]==dep[x]+1 ) {
int t = dfs(y,min(flow-sum,f)); // 優化1
sum += t;
e[i].f -= t;
e[i^1].f += t;
if ( sum==flow ) break; // 優化1
}
}
if ( sum==0 ) { // 如果sum==0，那麼這個點之前沒有增廣路，深度清零
dep[x] = 0;
}
return sum;
}
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
memset(head,-1,sizeof(head));
cnt = 0;
while ( m-- ) {
int u,v,f;
scanf("%d %d %d",&u,&v,&f);
addage(u,v,f); addage(v,u,0);
}
int ans = 0;
while ( bfs(s) ) { // 如果還存在增廣路繼續
ans += dfs(s,0x3f3f3f3f); // 加一條增廣路的值
}
printf("%d",ans);
return 0;
}
例題1 Dining POJ - 3281
Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.
Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.
Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.
Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).
Input
Line 1: Three space-separated integers: N, F, and D
Lines 2.. N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.
Output
Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes
Sample Input
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
Sample Output
3
Hint
One way to satisfy three cows is:
Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3
The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.
題意：有N頭牛，F種食物，D種飲料，每頭牛都有自己喜歡的食物和飲料，每種飲料和食物隻能配置設定給一頭牛。問：最多有多少頭牛能同時得到自己喜歡的食物和飲料。
思路：最大流建圖是把食物和飲料放在兩端。一頭牛拆分成兩個點，兩點之間的容量為1.喜歡的食物和飲料跟牛建條邊，容量為1.加個源點和彙點。源點與食物、飲料和彙點的邊容量都是1，表示每種食物和飲料隻有一個。這樣話完全是最大流問題了。
建圖：從源點向每個食物連一條邊，容量為1，
将牛拆成兩個點牛，牛'，中間連邊，容量為1
從食物向牛連邊，容量為1
連牛'和飲料，容量為1
連飲料和彙點，容量為1
源點-->food-->牛(左)-->牛(右)-->drink-->彙點
圖解：
再加上食物飲料和牛的關系，跑一邊源點到彙點的最大流dinic算法就得到答案了。
代碼：
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;
struct node {
int to,w,nxt;
};
const int maxn = 2e5+10;
node e[maxn];
int n,f,d;
int head[maxn];
int dep[maxn];
int cnt;
void addage( int u, int v, int w )
{
e[cnt].to = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt++;
}
int bfs(int node) // bfs分層
{
memset(dep,0,sizeof(dep)); // dep 層的深度
dep[node] = 1;
queue <int> Q;
Q.push(node);
while ( !Q.empty() ) {
int x = Q.front();Q.pop();
for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
int y = e[i].to,w = e[i].w;
if ( !dep[y] && w ) {
dep[y] = dep[x] + 1; // 編号++
Q.push(y);
}
}
}
return dep[f+d+2*n+1]; // return dep[t] ， 如果是0那麼說明沒有增廣路了，退出while
}
int dfs( int x, int flow ) // dfs找增廣路
{
if ( x==f+d+2*n+1 ) {
return flow;
}
int sum = 0;
for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
int y = e[i].to, w = e[i].w;
if ( w && dep[y]==dep[x]+1 ) {
int t = dfs(y,min(flow,w));// 注意dfs裡面的是min(flow，w)
flow -= t; // 目前的flow減t
sum+=t; // sum加t，就是上面減去的t。
e[i].w -= t; // 正向邊減t
e[i^1].w += t; // 反向邊加t
}
}
if ( sum==0 ) { // 如果sum==0，那麼這個點之前沒有增廣路，深度清零
dep[x] = 0;
}
return sum;
}
int main()
{
int i,j,u,v,w;
cnt = 0;
memset(head,-1,sizeof(head));
cin >> n >> f >> d;
// 源點0， 食物1~f, 飲料f+1~f+d, 牛f+d+1~f+d+2*n, 彙點f+d+2*n+1
for ( i=1; i<=f; i++ ) { // 建立源點和食物的關系
addage(0,i,1);
addage(i,0,0);
}
for ( i=1; i<=d; i++ ) { // 建立飲料與彙點的關系
addage(f+i,f+d+2*n+1,1);
addage(f+d+2*n+1,f+i,0);
}
for ( i=f+d+1; i<=f+d+2*n; i+=2 ) { // 建立牛之間的關系
addage(i,i+1,1);
addage(i+1,i,0);
}
for ( i=0; i<n; i++ ) {
int ai,bi,x;
cin >> ai >> bi;
for ( j=0; j<ai; j++ ) { // 建立食物和左牛的關系
cin >>x;
addage(x,f+d+1+2*i,1);
addage(f+d+1+2*i,x,0);
}
for ( j=0; j<bi; j++ ) { // 建立右牛和飲料的關系
cin >>x;
addage(f+d+2+2*i,f+x,1);
addage(f+x,f+d+2+2*i,0);
}
}
int ans = 0;
while ( bfs(0) ) { // 如果還存在增廣路繼續
ans += dfs(0,0x3f3f3f3f); // 加一條增廣路的值
}
printf("%d\n",ans);
return 0;
}
例題2 ： The Berland Championship Gym - 100694F
題意： 這裡有n個學生和m道題，第二行表示第i個學生最多能做幾道題，接下來是每個學生的名字，再有一個01矩陣，行代表學生，列代表題号，1就是會做，0是不會做。 現在讓你挑出3個學生要求他們能解出的題目最多。
Examples Input
5 5
3 2 2 3 1
Slava
Andrew
Egor
Denis
Sergey
11011
10100
00001
00100
10000
Output
5
Slava Andrew Egor
思路：剛開始想到的就是網絡流，s和學生連接配接，學生和他能解的題目連接配接，題目和t連接配接。但是 Time limit exceeded on test 10 ，顯然不能這樣建圖，看到大神的部落格提出，将題目給劃分成8個集合，這樣1000道題目，1000個點就可以簡化為8個點了，跑8個點肯定不會逾時。
000（沒有人可以做出的問題數量）
001（第一個人可以單獨做出的問題數量）
010（第二個人可以單獨做出的問題數量）
100（第三個人可以單獨做出的問題數量）
011（第一個人和第二個人都可以做出的問題數量）
101（第一個人和第三個人都可以做出的問題數量）
110（第三個人和第二個人都可以做出的問題數量）
111（第一二三個人都可以做出的問題數量）
将每個點都抽象出一個值來，正好對應上面8個值，方法是：如果第一個人會做tem+1， 如果第二個人會做tem+2，如果第三個人會做tem+4，最後用一個now數組來記錄每種類型的題目有幾個。
建圖方式：源點s和三個學生連接配接，流量為學生最多能解的題目； 三個學生和八個類型的題連接配接，流量為這種題的個數； 八種題和彙點t連接配接，流量為這種題的個數。
注意：在前向星存圖的時候直接在一個函數裡把正反邊都建出來，這題就因為反邊寫錯了wa了十幾遍，還有注意反邊的流量是零。
還有一個很玄學的地方，數組開了2e5跑了1825ms， 開2e4的數組隻跑了249ms
代碼：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct node {
int to,nxt,f;
}e[maxn];
int head[maxn],dep[maxn];
int now[10];
int s,t;
int student, problem;
string name[55];
int solve[55];
int cnt;
int a[55][1111];
void addage( int u, int v, int f )
{
e[cnt].to = v;
e[cnt].f = f;
e[cnt].nxt = head[u];
head[u] = cnt++;
e[cnt].to = u;
e[cnt].f = 0; // 這個地方是0！！！
e[cnt].nxt = head[v];
head[v] = cnt++;
}
int bfs( int v0 )
{
memset(dep,0,sizeof(dep));
queue <int> Q;
dep[v0] = 1;
Q.push(v0);
while ( !Q.empty() ) {
int x = Q.front(); Q.pop();
for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
int y = e[i].to, f=e[i].f;
if ( f&&dep[y]==0 ) {
dep[y] = dep[x] + 1;
Q.push(y);
}
}
}
return dep[t];
}
int dfs( int x, int flow )
{
if ( x==t ) {
return flow;
}
int sum = 0;
for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
int y = e[i].to, f=e[i].f;
if ( f&&dep[y]==dep[x]+1 ) {
int t = dfs(y,min(flow,f));
flow -= t;
sum += t;
e[i].f -= t;
e[i^1].f += t;
}
}
if ( sum==0 ) {
dep[x] = 0;
}
return sum;
}
int dinic()
{
int ans = 0;
while ( bfs(s) ) {
ans += dfs(s,0x3f3f3f3f);
}
return ans;
}
int main()
{
//ios::sync_with_stdio(0);
int i,j,k;
scanf("%d %d",&student,&problem);
for ( i=1;i<=student; i++ ) {
scanf("%d",&solve[i]);
}
for ( i=1;i<=student; i++ ) {
cin >> name[i];
}
for ( i=1; i<=student; i++ ) {
for ( j=1; j<=problem; j++ ) {
scanf("%1d",&a[i][j]);
}
}
int maxx = -125;
int Ans[3];
for ( i=1; i<=student; i++ ) {
for ( j=i+1; j<=student; j++ ) {
for ( k=j+1; k<=student; k++ ) {
s = 0; cnt = 0; t = 15;
memset(head,-1,sizeof(head));
memset(now,0,sizeof(now));
addage(s,1,solve[i]);
addage(s,2,solve[j]);
addage(s,3,solve[k]);
for ( int ii=1; ii<=problem; ii++ ) {
int tem = 0;
if ( a[i][ii]==1 ) {
tem += 1;
}
if ( a[j][ii]==1 ) {
tem += 2;
}
if ( a[k][ii]==1 ) {
tem += 4;
}
now[tem] ++; //枚舉每個問題有多少人能做，用上面的方法進行存儲
}
for ( int man=1; man<=3; man++ ) { //将人和集合連邊
for ( int ii=1; ii<=7; ii++ ) {
if ( man==1 && (ii==1||ii==3||ii==5||ii==7) ) {
addage(man,3+ii,now[ii]);
}
if ( man==2 && (ii==2||ii==3||ii==6||ii==7) ) {
addage(man,3+ii,now[ii]);
}
if ( man==3 && (ii==4||ii==5||ii==6||ii==7) ) {
addage(man,3+ii,now[ii]);
}
}
}
for ( int ii=1; ii<=7; ii++ ) { //集合和超級彙點連邊
addage(ii+3,t,now[ii]);
}
int now = dinic();
if ( now>maxx ) {
maxx = now;
Ans[0] = i;
Ans[1] = j;
Ans[2] = k;
}
}
}
}
printf("%d\n",maxx);
cout << name[Ans[0]] << " "<<name[Ans[1]] << " "<<name[Ans[2]] << endl;
return 0;
}