网络流

容量 c(x, y)
流量 f(x, y

最大流
从源点流向汇点的最大流量
增广路
所有边的剩余流量 $\ge$ 0
残留网
所有剩余流量 $\ge$ 0 的边以及节点构成的子图，包含正向边和反向边
反向边的容量 = 正向边的流量（相当于退回路径，表示这个流量我不要这么流了）

Dinic 求最大流

时间复杂度：$O(n{m}^2)$
需要注意如果存在多测以及二分这些，每次都需要重新构图！

步骤

通过 $bfs$ 对点分层，找增广路
通过 $dfs$ 多路增广

struct edge{
	int to; //终点
	int c; //容量
	int n; 	//反向边的编号
};
vector<edge> G[N];
vi d(N); //存点的深度
vi cur(N); //存 u 点的当前出边；
 
bool bfs(){ //其实就是找 s 到 t 的通路
	fill(d.begin(), d.end(), 0);
	queue<int> q;
	q.push(s); 
	d[s] = 1;
	while(q.size()){
		int u = q.front(); q.pop();
		for(auto x : G[u]){
			int v = x.to;
			if(x.c > 0 && d[v] == 0){
				d[v] = d[u] + 1;
				q.push(v);
				if(v == T) return true;
			}
		}
	}
	return flase;
}
 
int dfs(int u, int mf){
	if(u == t) return mf; //走到汇点
	int sum = 0;
	while(cur[u] < G[u].size()){
		int i = cur[u];
		int v = G[u][i].to;
		int t_c = G[u][i].c;
		int t_n = G[u][i].n;
		if(t_c > 0 && d[v] == d[u] + 1){
			int x = dfs(v, min(mf - sum, t_c));
			if(x){
				G[u][i].c -= x;
				G[v][t_n].c += x;
				sum += x;
				if(sum == mf) return sum;
				
			}else{
				cur[u] ++;
				}
		}else{
			cur[u] ++;
		}
	}
	return sum;
}
 
int dinic(){
	int flow = 0;
	while(bfs()){
		fill(cur.begin(), cur.end(), 0);
		flow += dfs(s, INF);
	}
	return flow;
}

数据读入

rep(i, 1, m){ 
	int a, b, e; cin >> a >> b >> e;
	G[a].push_back({b, e, G[b].size()});
	G[b].push_back({a, 0, G[a].size() - 1});
}

例题

大户爱的宿舍

题意
大户要给 $N$ 个学生分配宿舍，一间宿舍一共有 $k$ 个床位，每个学生都一个长为 $k$ 的字符串，如果 $s_i=1$ 代表这个学生愿意接受第 $i$ 个床位， 否则则不愿意接受
求大户最多能排满几间宿舍
$1\le N\le 1000$
$1\le k\le 30$

题解
一个有 $n$ 个学生，每个学生最终只会流向 $k$ 个床位的一个，求最终能开几件宿舍就是求流过每个宿舍的流量的最小值，每个学生的容量为 $1$
所以我们只需要求这个最小值的最大值

int n, k, t;
int s = 0;
struct edge{
	int to; 
	int c; 
	int n; 
};
 
vector<edge> G[N];
vi d(N);
vi cur(N); 
 
bool bfs(){
	fill(d.begin(), d.end(), 0);
	queue<int> q;
	q.push(s); 
	d[s] = 1;
	while(q.size()){
		int u = q.front(); q.pop();
		for(auto x : G[u]){
			int v = x.to;
			if(x.c > 0 && d[v] == 0){
				d[v] = d[u] + 1;
				q.push(v);
				if(v == t) return true;
			}
		}
	}
	return false;
}
 
int dfs(int u, int mf){
	if(u == t) return mf; 
	
    int sum = 0;
	while(cur[u] < G[u].size()){
		int i = cur[u];
		int v = G[u][i].to;
		int t_c = G[u][i].c;
		int t_n = G[u][i].n;
		
		if(t_c > 0 && d[v] == d[u] + 1){
			int x = dfs(v, min(mf - sum, t_c));
			
			if(x){
				G[u][i].c -= x;
				G[v][t_n].c += x;
				sum += x;
			
				if(sum == mf) return sum;
			}else{
				cur[u] ++;
			}
		}else{
			cur[u] ++;
		}
	}
	return sum;
}
int dinic(){
	int flow = 0;
	while(bfs()){
		fill(cur.begin(), cur.end(), 0);
		flow += dfs(s, INF);
	}
	return flow;
}
 
int check(int mid){ 
    int t_res = dinic();
    if(t_res == mid * k) return 1;
    else return 0;
}
void solve(){
    cin >> n >> k;
    t = n + k + 1;
    vector<string> ss(n + 1);
    rep(i, 1, n){
        cin >> ss[i];
        ss[i] = " " + ss[i];
    }
 
 
    int l = 0, r = n + 1;
    while(l < r){
        int mid = (l + r + 1) >> 1;
            rep(i, 1, n){
        G[0].push_back({i, 1, (int)G[i].size()}); 
        G[i].push_back({0, 0, (int)G[0].size() - 1});
        }
        rep(i, 1, n){
            rep(j, 1, k){
                if(ss[i][j] == '1'){
                    G[i].push_back({n + j, 1, (int)G[n + j].size()});
                    G[n + j].push_back({i, 0, (int)G[i].size() - 1});
                }
            }
        }
 
        rep(i, n + 1, n + k){
            G[i].push_back({n + k + 1, mid, (int)G[n + k + 1].size()});
            G[n + k + 1].push_back({i, 0, (int)G[i].size() - 1});
        }
        if(check(mid)){
            l = mid;
        }else{
            r = mid - 1;
        }
        rep(i, 0, n + k + 1) G[i].clear();
    }
 
    cout << l << endl;
    return;
}   

最小割

最小割的划分
标记为 1 的和源点一组， 标记为 0 的和汇点一组

void mincut(int u){
	vis[u] = 1;
	for(auto x : G[u]){
		if(vis[x.to] == 0 && x.c > 0) mincut(x.to);
	}
	return;
}

最小割的最小边数(只关心边数，实际上不是最小割！！！)

rep(i, 1, n) G[i].clear();
rep(i, 1, m){
	G[a[i]].push_back({b[i], 1, (int)G[b[i]].size()});
	G[b[i]].push_back({a[i], 0, (int)G[a[i]].size() - 1});
}
 
cout << dinic() << endl;

求最小割情况下割的边数

int M = m + 2; //将 M 设置为严格大于整个图的边数即可
 
//读入时的操作：
rep(i, 1, m){
	G[a[i]].push_back({b[i], e[i] * M + 1, (int)G[b[i]].size()});
	G[b[i]].push_back({a[i], 0, (int)G[a[i]].size() - 1});
}
 
int res = dinic();
int flow = res / M; //容量
int cnt = res % M; //边数

费用流

最小费用最大流 ： 总花费最小的最大流
最大费用最大流 ： 总花费最大的最大流
无论是哪一种都是在最大流的情况下考虑费用，最大流的值只有一个，但是路径会有很多种

采用 $EK$ 算法

最小费用模板

如果需要使用最大费用，将 $d$ 数初始化为 $-INF$ , 然后在标注的这一行的条件
改成 $if(c>0\&\&d[v]<d[u]+w)$

struct edge{
	int to;
	int c;
	int w; 
	int n;
};
vector<edge> G[N];
vi d(N), mf(N), pre_v(N), pre_e(N), vis(N);
int flow = 0, cost = 0;
 
bool spfa(){
	fill(d.begin(), d.end(), INF); //这里也要改成 -INF
	fill(mf.begin(), mf.end(), 0);
	queue<int> q;
	q.push(s);
	d[s] = 0;
	mf[s] = INF;
	vis[s] = 1;
	while(q.size()){
		int u = q.front(); q.pop();
		vis[u] = 0；
		rep(i, 0, G[u].size() - 1){
			int v = G[u][i].to;
			int c = G[u][i].c;
			int w = G[u][i].w;
			if(c > 0 && d[v] > d[u] + w){    //这一行
				d[v] = d[u] + w;
				mf[v] = min(mf[u], c);
				pre_v[v] = u;
				pre_e[v] = i;
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	return mf[t] > 0;
} 
 
void EK(){
	while(spfa()){
		int v = t;
		while(v != s){
			int u = pre_v[v];
			int i = pre_e[v];
			int nn = G[u][i].n;
			G[u][i].c -= mf[t];
			G[v][nn].c += mf[t];
			v = u;
		}
		flow += mf[t];
		cost += mf[t] * d[t];
	}
}