网络流
一些定义：
网络是指一个特殊的有向图 G = (V, E), 其与一般有向图的不同之处， 在与有容量和源汇点。
- 每条边 (u, v) 都有一个容量的权值，记作 $c(u, v)$。当(u, v) $\notin E$时，可以假定c(u, v) = 0.
对于流，顾名思义，其有以下性质：
-
- 容量限制： $0 <= f(u,v) <= c(u, v).$
-
- 流守恒性：$f(u) = \sum_{x\in V}f(u,x)-\sum_{x\in V}f(x,u).$
对于割，如果网络 G = (V, E)， 如果 {S, T} 是 V 的划分 (即 $S \cup T = V, S \cap T=\ empty $)，且满足 $s \in S, t \in T$, 则称{S, T} 是 G的一个 s-t 割。
常见问题：
- 最大流问题：使得网络流图的流尽可能大。
- 最小割问题：使得当前找到的割容量最小。
- 最小费用最大流：对每条边上给定一个权值 w(u, v)， 称为费用。含义是单位流量通过 (u, v)所花费的代价。对G所有可能得最大流，称其总费用最小的一者为最小费用最大流。
最大流：
1.FF：
FF增广是计算最大流的一类算法的总称，采用贪心的思想，通过寻找增广路来更新求解最大流。
其时间复杂度的上界是，O($|E||f|$).
以下的EK算法是具体体现。
2.EK:
如果在G 上我们从 源点 找到了一条到汇点的路，记录路上的最小容量， 最后从汇点方向对每条经过的路增加 $\delta$ 的流
量。一直进行下去知道没有到汇点的路存在。
显然，单轮增广的时间限制是 O(E). 增广的时间复杂度是 O(V * E * E)。其中 V 是点数， M是边数。
代码：
struct Edge{
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f){}
};
struct EK{
const static int maxn = 250;
const static int inf = 1e9;
// O(nm^2)
int n, m;
vector<Edges> edges;
vector<int> G[maxn];
int a[maxn], pre[maxn];
void init(int n){
for(int i = 1; i <= n; i ++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap){
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2); // G: 存边的下边 // 0
G[to].push_back(m - 1); // 1
}
int MaxFlow(int S, int T){
int flow = 0;
while(1){
memset(a, 0, sizeof a);
queue<int> q;
q.push(S);
a[S] = INF;
// 寻找增广路
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = 0; i < G[x].size(); i ++){
Edge &e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow){
pre[e.to] = G[x][i]; // G[x][i] 是 最接近 e.to 的边
a[e.to] = min(a[x], e.cap - e.flow);
q.push(e.to);
}
}
if(a[T]) break; // 找到增广 -> T点接收到流
}
if(!a[T]) break;
for(int u = T; u != S; u = edges[pre[u]].from){
edges[pre[u]].flow += a[u]; // 增加可行
edges[pre[u] ^ 1].flow -= a[u]; // 减小反向
}
flow += a[T];
}
return flow;
}
};
3.Dinic:
在DFS中，从S开始，每次下一层次随便找一个点，直到到达T，然后再一层一层回溯回去，继续找这一层的另外的点再往下搜索
这样就满足了我们同时求出多条增广路的需求！
-
Dinic算法框架
-
在残量网络BFS求出节点的层次，构造分层图
-
在分层图上DFS寻找增广路，在回溯时同时更新边权
-
适用范围
时间复杂度，$O(n*n*m)$一般能够处理$10^4-10^5$规模的网络
相较于EK算法，显然Dinic算法的效率更优也更快：虽然在稀疏图中区别不明显，但在稠密图中Dinic的优势便凸显。
弧优化：
考虑到当 图中某点 u 其有大量的 入边 与 出边那么其时间复杂度可能会达到$O(|E|^2)$,由此采用弧优化，记录当前边如果流满，该流向的下一条边。
代码：
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<int>> h;
vector<int> cur, dep, vis;
Dinic(int n) : n(n + 1), h(n + 1) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (int &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
// reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void mincut(int u){
vis[u] = 1;
for(int &i = cur[u]; i < h[u].size(); i ++){
int j = h[u][i];
T v = ver[j].to, c = ver[j].w;
if(!vis[v] && c){
mincut(v);
}
}
}
void Mincut(int s){
vis.assign(n + 1, 0);
mincut(s);
}
};
using Flow = Dinic<ll>;
以上都是通过增广路的方法去寻找最大流，实际上还有更优的PR预流推进算法 ISAP 与 HLPP
4.ISAP:
struct Edge {
ll from, to, cap, flow;
Edge(ll u, ll v, ll c, ll f) : from(u), to(v), cap(c), flow(f) {}
};
bool operator<(const Edge& a, const Edge& b) {
return a.from < b.from || (a.from == b.from && a.to < b.to);
};
struct ISAP{
// O(N * N * M)
const int maxn = 1e3 + 10;
const ll INF = 1e18;
int n, m, S, T;
ISAP(int _n, int _m, int _S, int _T): n(_n), m(_m), S(_S), T(_T){}
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
ll d[maxn], cur[maxn], p[maxn], num[maxn];
void AddEdge(ll from, ll to, ll cap){
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(t);
vis[t] = 1, d[t] = 0;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i] ^ 1];
if (!vis[e.from] && e.cap > e.flow) {
vis[e.from] = 1;
d[e.from] = d[x] + 1;
Q.push(e.from);
}
}
}
return vis[s];
}
void init() {
for (int i = 1; i <= n; i++) G[i].clear();
edges.clear();
}
int Augment() {
int x = t, a = INF;
while (x != s) {
Edge& e = edges[p[x]];
a = min(a, e.cap - e.flow);
x = edges[p[x]].from;
}
x = t;
while (x != s) {
edges[p[x]].flow += a;
edges[p[x] ^ 1].flow -= a;
x = edges[p[x]].from;
}
return a;
}
ll Maxflow() {
ll res = 0;
BFS();
meset(num, 0, sizeof(num));
for (int i = 1; i <= n; i++) num[d[i]]++;
int x = S;
memset(cur, 0, sizeof(cur));
while (d[s] < n) {
if (x == t) {
flow += Augment();
x = s;
}
int ok = 0;
for (int i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (e.cap > e.flow && d[x] == d[e.to] + 1) {
ok = 1;
p[e.to] = G[x][i];
cur[x] = i;
x = e.to;
break;
}
}
if (!ok) {
int m = n;
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (e.cap > e.flow) m = min(m, d[e.to]);
}
if (--num[d[x]] == 0) break;
num[d[x] = m + 1]++;
cur[x] = 0;
if (x != s) x = edges[p[x]].from;
}
}
return res;
}
}
5.HLPP
template <typename T> struct HLPP {
const int inf = 0x3f3f3f3f;
const T INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int to, cap, flow, anti;
Edge(int v = 0, int w = 0, int id = 0) : to(v), cap(w), flow(0), anti(id) {}
};
vector<vector<Edge>> e;
vector<vector<int>> gap;
vector<T> ex; // 超额流
vector<bool> ingap;
vector<int> h;
int n, gobalcnt, maxH = 0;
T maxflow = 0;
HLPP(int n) : n(n), e(n + 1), ex(n + 1), gap(n + 1) {}
void AddEdge(int u, int v, int w) {
e[u].push_back({v, w, (int)e[v].size()});
e[v].push_back({u, 0, (int)e[u].size() - 1});
}
void PushEdge(int u, Edge &edge) {
int v = edge.to, d = min(ex[u], 1LL * edge.cap - edge.flow);
ex[u] -= d;
ex[v] += d;
edge.flow += d;
e[v][edge.anti].flow -= d;
if (h[v] != inf && d > 0 && ex[v] == d && !ingap[v]) {
++gobalcnt;
gap[h[v]].push_back(v);
ingap[v] = 1;
}
}
void PushPoint(int u) {
for (auto k = e[u].begin(); k != e[u].end(); k++) {
if (h[k->to] + 1 == h[u] && k->cap > k->flow) {
PushEdge(u, *k);
if (!ex[u]) break;
}
}
if (!ex[u]) return;
if (gap[h[u]].empty()) {
for (int i = h[u] + 1; i <= min(maxH, n); i++) {
for (auto v : gap[i]) {
ingap[v] = 0;
}
gap[i].clear();
}
}
h[u] = inf;
for (auto [to, cap, flow, anti] : e[u]) {
if (cap > flow) {
h[u] = min(h[u], h[to] + 1);
}
}
if (h[u] >= n) return;
maxH = max(maxH, h[u]);
if (!ingap[u]) {
gap[h[u]].push_back(u);
ingap[u] = 1;
}
}
void init(int t, bool f = 1) {
ingap.assign(n + 1, 0);
for (int i = 1; i <= maxH; i++) {
gap[i].clear();
}
gobalcnt = 0, maxH = 0;
queue<int> q;
h.assign(n + 1, inf);
h[t] = 0, q.push(t);
while (q.size()) {
int u = q.front();
q.pop(), maxH = h[u];
for (auto &[v, cap, flow, anti] : e[u]) {
if (h[v] == inf && e[v][anti].cap > e[v][anti].flow) {
h[v] = h[u] + 1;
q.push(v);
if (f) {
gap[h[v]].push_back(v);
ingap[v] = 1;
}
}
}
}
}
T Maxflow(int s, int t) {
init(t, 0);
if (h[s] == inf) return maxflow;
h[s] = n;
ex[s] = INF;
ex[t] = -INF;
for (auto k = e[s].begin(); k != e[s].end(); k++) {
PushEdge(s, *k);
}
while (maxH > 0) {
if (gap[maxH].empty()) {
maxH--;
continue;
}
int u = gap[maxH].back();
gap[maxH].pop_back();
ingap[u] = 0;
PushPoint(u);
if (gobalcnt >= 10 * n) {
init(t);
}
}
ex[s] -= INF;
ex[t] += INF;
return maxflow = ex[t];
}
};
using Flows = HLPP <int>;
题集：
1.Poj1149
2.Poj1637
3.Poj2391
4.Poj3281
5.Joj2453
6.Sgu 438: 动态流建模
题目大意：
现在有 n 个人过河。 河流宽为 W，河上有 m 块石头，给出石头的坐标（x, y）和容纳的人数 ci。
现在 M 个人一下能跳距离 D。问最少要多少时间全部过河。 跳一步一秒。
解：
首先容易想到可以利用最大流判断是否能通过。但是这样我们没法知道最小时间。由此从别的角度出发。过河的总时间不会超过 （N + M） 那么可以通过，把每个石头在每个时间点 t 都分成两个 （P, P’, Ci）。
二分时间。然后枚举该时间。对每个时间 t 的石头， 找到 所有距离 <= D 的 石头。对网络流加边：(P, t) -> (Q, t + 1, inf).
(Q, t) -> (P, t + 1, inf)。
然后我们现在的最大流就是当前时间能够通过的最大人数。其满足了我们在每个时间内每块石头的流量都没有超过其最大容量。而且对时间顺序的建边，每个时间 t 都 只是能 走到下一个时间 t + 1。满足了我们的题目要求。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 55 * 105 * 2;
const int MAXE = MAXN * 500;
const int INF = 0x7fff7fff;
struct Dinic {
int n, m, st, ed, ecnt;
int vis[MAXN], head[MAXN];
int cur[MAXN], d[MAXN];
int to[MAXE], next[MAXE], flow[MAXE];
void init(){
memset(head,0,sizeof(head));
ecnt = 2;
}
void addEdge(int u,int v,int f) {
to[ecnt] = v; flow[ecnt] = f; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++;
}
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int> que; que.push(st);
d[st] = 0; vis[st] = true;
while(!que.empty()){
int u = que.front(); que.pop();
for(int p = head[u]; p; p = next[p]){
int v = to[p];
if (!vis[v] && flow[p] > 0){
vis[v] = 1;
d[v] = d[u] + 1;
que.push(v);
if(v == ed) return true;
}
}
}
return vis[ed];
}
int dfs(int u, int a) {
if(u == ed || a == 0) return a;
int outflow = 0, f;
for(int &p = cur[u]; p; p = next[p]){
int v = to[p];
if(d[u] + 1 == d[v] && (f = dfs(v, min(a, flow[p]))) > 0){
flow[p] -= f;
flow[p ^ 1] += f;
outflow += f;
a -= f;
if(a == 0) break;
}
}
return outflow;
}
int Maxflow(int ss, int tt, int nn) {
st = ss; ed = tt;
int ans = 0;
while(bfs()){
for(int i = 0; i <= ed; ++i) cur[i] = head[i];
ans += dfs(st, INF);
}
return ans;
}
} G;
const int MAX = 55;
struct Point {
int x, y, c;
};
int dis2(const Point &a, const Point &b) {
int xx = a.x - b.x, yy = a.y - b.y;
return xx * xx + yy * yy;
}
int n, m, d, w;
Point rub[MAX];
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define get_num(i, t) ((i - 1) * 2 * (mid - 1) + 2 * (t - 1) + 1)
void solve() {
int left = 1, right = n + m + 1;
while(left < right) {
int mid = (left + right) >> 1;
int ss = n * (mid - 1) * 2 + 1, st = ss + 1, tt = ss + 2;
G.init();
G.addEdge(st, ss, m);
FOR(i, 1, n) {
if(rub[i].y <= d) {
FOR(t, 1, mid - 1) G.addEdge(ss, get_num(i, t), INF);
}
if(rub[i].y + d >= w) {
FOR(t, 1, mid - 1) G.addEdge(get_num(i, t) + 1, tt, INF);
}
}
FOR(i, 1, n) FOR(t, 1, mid - 1) {
int num = get_num(i, t);
G.addEdge(num, num + 1, rub[i].c);
if(t < mid - 1) G.addEdge(num + 1, num + 2, INF);
}
FOR(i, 1, n) FOR(j, 1, n) {
if(i == j || dis2(rub[i], rub[j]) > d * d) continue;
FOR(t, 1, mid - 2) G.addEdge(get_num(i, t) + 1, get_num(j, t + 1), INF);
}
int ans = G.Maxflow(st, tt, tt);
if(ans < m) left = mid + 1;
else right = mid;
//printf("%d %d\n", mid, ans); system("pause");
}
if(right == n + m + 1) puts("IMPOSSIBLE");
else printf("%d\n", right);
}
int main() {
scanf("%d%d%d%d", &n, &m, &d, &w);
FOR(i, 1, n) scanf("%d%d%d", &rub[i].x, &rub[i].y, &rub[i].c);
FOR(i, 1, n) if(rub[i].c > m) rub[i].c = m;
if(w <= d) printf("1\n");
else solve();
}
最小割
定义：
-
割：将所有的点划分为两个集合，其中原点 属于 S, 汇点 t 属于 T, 对于任意一个割 （S, T）。都会使得网络断流。
-
割的容量： c(S, T) 表示从 S 到 T 的 出边容量之和。
- 最小割：顾名思义就是求一个割 (S, T) 。使得割的容量 c（S, T）最小。方案不唯一。
定理：
- 最大流最小割定理：$f(s,t)_{max}=c(s,t)_{min}$.
证明：假设最小割 < 最大流。此时，网络流还没有达到最大，还能找到 S->T 的增广路。与定义相悖。
问题：
-
求最小割
-
求最小割的划分
-
求最小割的最少边数
问题1：实际就是最大流即可。
问题2：跑完最大流之后，此时满流的边即是割边，从源点开始对残余网络深搜即可。就是S的划分。
问题3：将边权全部化为1后，再跑一次网络流即可。
实际最小割还是转化成最大流的问题去处理。
题目：
1.【模板】最小割树：
对于多次询问两点之间的最小割，可以利用分治每次任意求两个点的最小割，然后将源点 与 汇点分为两块，将其用最小割连接。这样一直进行下去，我们可以得到一颗最小割树。
其中，在树上两点之间的最小割就是他们简单路径上的最小值。
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<int>> h;
vector<int> cur, dep, vis;
Dinic(int n) : n(n + 1), h(n + 1) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (int &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void mincut(int u){
vis[u] = 1;
for(int &i = cur[u]; i < h[u].size(); i ++){
int j = h[u][i];
T v = ver[j].to, c = ver[j].w;
if(!vis[v] && c){
mincut(v);
}
}
}
void Mincut(int s){
vis.assign(n + 1, 0);
mincut(s);
}
};
using Flow = Dinic<ll>;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// int T; cin >> T; while(T --) solve();
int n, m; cin >> n >> m;
n ++;
Dinic<ll> Flows(n + 1);
vector<vector<pair<int, int>>> G(n + 2);
vector<int> v(n + 2, 0), t(n + 2, 0);
for(int i = 1; i <= m; i ++){
ll a, b, c; cin >> a >> b >> c;
a ++, b ++;
Flows.AddEdge(a, b, c);
Flows.AddEdge(b, a, c);
}
auto build = [&] (auto && build, int l, int r) -> void {
if(l >= r) return ;
int S = v[l], T = v[l + 1];
ll w = Flows.Maxflow(S, T);
G[S].push_back({T, w});
G[T].push_back({S, w});
// cout << w << " " << S << " " << T << endl;
int pl = l, pr = r;
for(int i = l; i <= r; i ++){
if(Flows.dep[v[i]] != -1){
t[pl ++] = v[i];
}else{
t[pr --] = v[i];
}
}
for(int i = l; i <= r; i ++) v[i] = t[i];
build(build, l, pl - 1); build(build, pl, r);
};
for(int i = 1; i <= n; i ++) v[i] = i;
build(build, 1, n);
auto dfs = [&] (auto && dfs, int u, int fa, int tar) -> int {
for(auto &[v, w] : G[u]){
if(v == fa) continue;
if(v == tar) return w;
int val = dfs(dfs, v, u, tar);
if(val != -1) return min(w, val);
}
return -1;
};
int q; cin >> q;
while(q --){
int a, b; cin >> a >> b;
a ++, b ++;
cout << dfs(dfs, a, -1, b) << endl;
}
return 0;
}
2.Hoj 2634
题意：有m个项目和n个员工，做项目i可以获得Ai 元，必须雇佣若干个指定的员工。雇佣员工 j 需要花费BJ元。一旦雇佣，员工 j 可以参加多个项目的开发。最多能挣多少钱。(1 <= M, N <= 100)
解：
原点与员工相连，项目与汇点相连。将项目与员工之间连接（i, j, INF）。最后结果是 $\sum{A_i} - Maxflow$
最大权闭合子图模型：
存在一个图的子图，使得子图中的所有点的出度指向的点依旧在这个子图内。
图中每个点具有点权值，在他的所有闭合子图中，点权之和最大的即是最大权闭合子图。
证明：
最小割一定是简单割。（割（S, T）中的每一条边都与 S 或者 T 相关联。）。因为图中将所有与 S相连的点放
入割集就可以得到一个割，且不为正无穷。因此最小割一定不包含正无穷的边。
由此知道，最小割对应了一个闭合子图。接下来证明最小割是最大权的闭合子图。
我们所选择的那部分子图，权值和 = 所有正权值之和 - 我们未选择的正权值点的权值之和 + 我们未选择的负权值点的权值之和。
当我们不选择一个正权值点的时候，其与 s 的连边就会断开；当我们选择一个负权值点的时候，其与 t 的连边就会断开。
由此转化为：权值和 = 所有正权值之和 - 割的容量。
于是，得出结论：最大权值和 = 所有正权值之和 - 最小割。
3.Hoj 2713
题目大意:
一个N*M的网格，每个单元都有一块价值Cij的宝石。问最多能取多少价值的宝石且任意两块宝石不相邻。（1 <= N, M <= 50, 0 <= Cij <= 40000）
解：
经典最大点权独立集（最小点权覆盖）：两者为对偶问题，所以只需解决最小点权覆盖问题：
其问题指的是：在图中选取一些点，满足图中每条边连接的两个点中，至少一个被选择，求所选取的点的最小权值和。
先考虑将网格黑白染色，从源点到每个黑点都有一条边，每个白点到汇点都有一条边。容量均为宝石的价值。
每个黑点向其相邻的四个白点连边。容量为 INF。（转化为最小割，就是不能包含这样的选择）。设最小割为
Maxflow, 最后答案 ans = $\sum{C_{ij}} - MaxFlow$。
4. 确定最小割唯一：
求一次最大流后，在残余网络中R，以正向弧对S, 逆对T作DFS, 这次用一个 flag[i]，标记点i是否在两次DFS中被探访过，扫一遍所有点，如果没有被探访过的点的话，说明最小割不唯一。
5.无向图点带权的连通度问题：
【题目大意】 一个犯罪团伙打算去偷一家美术馆。警察决定派K个人堵住所有从匪窝通向美术 馆的道路，不过他们只能驻守在沿途顶点处而不能在匪窝或美术馆，且每个点都 有一个需要警察驻守的最低人数Ri。问警察能否完成任务。（2 < N <= 100, 1 < M <= 10000）
【建模方法】 此题是无向图点带权的点连通度问题。将每个点i拆成两个点i’, i’’，除匪窝s和 美术馆t外加边(i’, i’’, Ri)，将每条无向边(i, j)分解为(i’’, j’), (j’’, i’)。令 s’’为源，t’为 汇，求一次最小割即为结果。（注意此题还需要特判匪窝和美术馆在同一点的情 况）
发散思维：
(1) 如果警察只能驻守在边上，该如何做？
直接以原图为网络求最小割即可。
(2) 如何求无向图的边连通度？
任选一点固定为源，枚举汇点求最小割，取最小值即为所求。
(3) 如何求无向图的点连通度？
令本题中的Ri = 1，以度最小的顶点为源，枚举汇点求最小割，取一个最小值即 为所求。
6. Spoj 839 Optimal Marks: 0 / 1 划分集合建图
【题目大意】：给出一个无向图，每个点有一个标号 mark[i]，不同点可能有相同的标号。对于 一条边(u, v)，它的权值定义为mark[u] xor mark[v]。现在一些点的标号已定，请 决定剩下点的标号，使得总的边权和最小。（0 < N <= 500, 0 <= M <= 3000, 0 <= mark[i] <= 2^31-1）
#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int M=70005;
const int INF=2147483647;
struct edge{
int v,w,nxt;
}edge[M<<1];
int head[N],cur[N],cnt=1;
struct node{
int u,v;
}a[M];
int _;
int n,m,k;
int s,t;
int dep[N],ans[N],val[N],vis[N];
void addedge(int u,int v,int w){
edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].nxt=head[u],head[u]=cnt;
}
void Add(int x){
memset(head,0,sizeof(head)),cnt=1;
for(int i=1;i<=n;i++){
if(~val[i]){
if((val[i]>>x)&1) addedge(s,i,INF),addedge(i,s,0);
else addedge(i,t,INF),addedge(t,i,0);
}
}
for(int i=1;i<=m;i++){
addedge(a[i].u,a[i].v,1),addedge(a[i].v,a[i].u,0);
addedge(a[i].v,a[i].u,1),addedge(a[i].u,a[i].v,0);
}
}
int bfs(){
for(int i=s;i<=t;i++) dep[i]=INF,cur[i]=head[i];
queue<int> q;
q.push(s),dep[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v,w=edge[i].w;
if(dep[v]==INF&&w){
dep[v]=dep[u]+1;
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int lim){
if(u==t) return lim;
int flow=0;
for(int i=cur[u];i;i=edge[i].nxt){
cur[u]=i;
int v=edge[i].v,w=edge[i].w;
if(dep[v]==dep[u]+1&&w){
int delta=dfs(v,min(lim-flow,w));
if(!delta) dep[v]=INF;
edge[i].w-=delta;
edge[i^1].w+=delta;
flow+=delta;
if(flow==lim) break;
}
}
return flow;
}
void find(int u,int x){
vis[u]=1,ans[u]+=x;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v,w=edge[i].w;
if(!vis[v]&&edge[i].w) find(v,x);
}
}
void dinic(int x){
for(int i=s;i<=t;i++) vis[i]=0;
while(bfs()) dfs(s,INF);
find(s,(1<<x));
}
void solve(){
scanf("%d%d",&n,&m),t=n+1;
for(int i=1;i<=n;i++) val[i]=-1,ans[i]=0;
for(int i=1;i<=m;i++) scanf("%d%d",&a[i].u,&a[i].v);
scanf("%d",&k);
for(int i=1,x;i<=k;i++){
scanf("%d",&x);
scanf("%d",&val[x]);
}
for(int i=0;i<=30;i++){
Add(i);
dinic(i);
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
int main(){
scanf("%d",&_);
while(_--) solve();
return 0;
}
7. “二者取其一”：
【题目大意】：
N个城堡守卫正在就非洲的燕子能否搬运椰子而进行投票。每个人都有自己的看法，但是为了避免跟自己的朋友持相反意见，他们时常会投相反的票。现在给出每个人的初始看法以及朋友关系，求在某种投票方案下，违背自己意愿的票数与持不同意见的朋友对数的总和最小。
【解】：
对意见不同的人分别与 S, T 相连。然后求一次最大流表明答案。
【扩展】：
假如我们有这样一个函数：
$ F(x_1,x_2,....x_n)= \sum_{i=1}^{n}(1-x_i)*|p_i-v_0| + \sum_{i=1}^{n}x_i*|p_i-v_1| + \sum_{i=1}^{n} |x_i-x_j| *|p_i-p_j|$
其中，pi, v0, v1 均为常数。xi = 0 或 1。
我们将前两项和起来考虑：要么xi=0并获得一个|pi-v0|， 要么xi=1并获得一个|pi-v1|；考虑第三项，如果xi, xj取不同值时获得一个|pi-pj|。 构图思路和之前一模一样，求一次最小割即为结果。
小结：
最小割的应用，有几类特点：
（1）：用s-t割表示方案，对应着原本的意义。
（2）：最大权闭合子图 \ 最小独立集覆盖;
如果对于 “要做A必须做B” 这样的蕴含关系，可以考虑将其建边 (A, B, inf) 。这样表示A, B 不可分割。
（3）：二者取其一问题：
每个点有两种方案供选择，必须选择其中一种，如果两点之间选择了不同的方案，还会产生额外的费用。
有上下界
无源汇上下界可行流:
给定无汇源网络G，询问是否存在一种标定每条边流量的方式。使得每条边流量满足上下界的同时，每一个点流量平衡。
换言之：寻找一种可行流，使得每条边满足上下界的同时，每个点入\ 出流量守恒。
假设每条边已经有了 b(u, v) 的流量。设其为初始流。同时我们在新图中加入 u 连向 v 的流量为 c(u,v) - b(u,v)的边。考虑在新图上进行调整。
由于最大流需要满足初始流量平衡条件（最大流可以看做下界为 0 的上下界最大流）。但是构造出来的初始流很有可能不满足初始流量平衡。
假设一个点初始流入、流出流量差为 M :
- M = 0, 此时流量平衡，不需要附加边。
- M > 0, 此时入流量大，则需要新建附加源点S‘，向其连流量为 M的附加边。
- M < 0, 此时出流量大，则需要新建附加汇点T’，向其连流量为 -M的附加边。
如果附加边满流，说明这一个点的流量平衡条件可以满足。
【算法步骤】
- 令每条边的流量都等于下界，得到一个初始流，建出流的残余网络（每条边的流量等于上下限之差）。
- 记 A[i] 表示：i 在初始流中流入量 - 流出量，ss 表示虚拟原点，tt表示虚拟汇点。接下来要找一条附加流，使得其与我们初始流合并后，满足流量守恒。
- 若A[i] > 0, 说明在附加流中，流入< 流出。需要让多的流出量有一个来路。由此建一条 (ss, i, |A[i]|)的边。同理，A[i] < 0，则建一条(i, tt, |A[i]|) 的边。
- 如果能够找到一个流满足新加的边都满流。这个流在我们原图上的部分就是需要的附加流。可以发现：如果存在，这样的流一定是我们所建出的图的 ss – tt 的最大流, 跑 ss - tt 最大流即可。
- 如果最大流的大小等于ss出发的所有边的流量上限之和，则存在这样的附加流满足题意。
- 每条边的容量 = 容量下界 + 附加流中的流量（跑完dinic之后的反向边权。
【模板】
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<T>> h;
vector<T> cur, dep;
Dinic(int n) : n(n + 1), h(n + 2) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (int &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
// reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void Clear(){
for(int i = 0; i <= n; i ++) h[i].clear();
ver.clear();
}
};
using Flow = Dinic<int>;
const int N = 1e5 + 10;
int A[N], now[N], rid[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int Case; cin >> Case; while(Case --){
int n, m; cin >> n >> m;
int ss = 0, tt = n + 1;
Flow flows(n + 1);
for(int i = 1; i <= m; i ++){
int a, b, l, r; cin >> a >> b >> l >> r;
now[i] = l;
A[b] += l, A[a] -= l;
flows.AddEdge(a, b, r - l);
rid[i] = (int)flows.ver.size() - 1;
}
int sum = 0;
for(int i = 1; i <= n; i ++){
if(A[i] > 0) flows.AddEdge(ss, i, A[i]), sum += A[i];
if(A[i] < 0) flows.AddEdge(i, tt, -A[i]);
}
int res = flows.Maxflow(ss, tt), ok = 1;
if(res != sum){
ok = 0;
}
if(ok){
cout << "YES" << endl;
L(i, 1, m) cout << now[i] + flows.ver[rid[i]].w << endl;
}else{
cout << "NO" << endl;
}
L(i, 1, n) A[i] = 0;
flows.Clear();
}
return 0;
}
有源汇上下界可行流：
给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。
假设原点为 S, 汇点为 T。我们可以加入一条 T 到 S 的上界为INF, 下界为0的边。转化为无源汇上下界可行流问题。
若有解，则 S 到 T的可行流等于 T 到 S 的附加边流量。
代码见有源汇上下界最大流。
有源汇有上下界最大流：
现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制，在这些前提下要求流量最大。
首先求出一个有源汇上下界可行流，此时流不一定最大，再在残余网络上跑一遍 s - t最大流即可。最终的最大流 = 可行流 + 残余 s - t 最大流。
【模板】
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<T>> h;
vector<T> cur, dep;
Dinic(int n) : n(n + 1), h(n + 2) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (T &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
// reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void Clear(){
for(int i = 0; i <= n; i ++) h[i].clear(); // S ~ T
ver.clear();
}
};
using Flow = Dinic<ll>;
const int N = 1e5 + 10;
const ll inf = 1e18;
int A[N], rid[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// int T; cin >> T; while(T --) solve();
int n, m, a, b; cin >> n >> m >> a >> b;
ll S = 0, T = n + 1, sum = 0;
Flow flows(n + 1);
for(int i = 1; i <= m; i ++){
int x, y, l, r; cin >> x >> y >> l >> r;
A[y] += l, A[x] -= l;
flows.AddEdge(x, y, r - l);
rid[i] = (int)flows.ver.size() - 1;
}
for(int i = 1; i <= n; i ++){
if(A[i] > 0) flows.AddEdge(S, i, A[i]), sum += A[i];
if(A[i] < 0) flows.AddEdge(i, T, -A[i]);
}
flows.AddEdge(b, a, inf);
ll res = flows.Maxflow(S, T), ed = (int)flows.ver.size() - 1;
if(res != sum){
cout << "please go home to sleep" << endl;
}else{
S = a, T = b;
ll ans = flows.ver[ed].w; // 有源汇上下界可行流。
flows.ver[ed].w = flows.ver[ed - 1].w = 0; // 剩下的残余网络。
cout << ans + flows.Maxflow(S, T) << endl;
}
return 0;
}
【例1：P5192】
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<T>> h;
vector<T> cur, dep;
Dinic(int n) : n(n + 1), h(n + 2) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (T &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
// reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void Clear(){
for(int i = 0; i <= n; i ++) h[i].clear(); // S ~ T
ver.clear();
}
};
using Flow = Dinic<ll>;
const ll inf = 1e18;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
while(cin >> n >> m){
int s = 0, t = n + m + 1, S = n + m + 2, T = S + 1;
ll sum = 0;
vector <ll> c(n + m + 3, 0);
Flow flows(n + m + 3);
for(int i = 1; i <= m; i ++){
int G; cin >> G;
c[i] -= G, c[t] += G; // (g ~ inf)
flows.AddEdge(i, t, inf - G);
}
for(int i = m + 1; i <= n + m; i ++){
int C, D; cin >> C >> D;
flows.AddEdge(s, i, D); // (0 ~ D)
while(C --){
int id, l, r; cin >> id >> l >> r;
id ++;
c[id] += l, c[i] -= l;
flows.AddEdge(i, id, r - l);
}
}
for(int i = 0; i <= n + m + 1; i ++){
if(c[i] > 0) flows.AddEdge(S, i, c[i]), sum += c[i];
if(c[i] < 0) flows.AddEdge(i, T, -c[i]);
}
flows.AddEdge(t, s, inf);
int ed = flows.ver.size() - 1;
ll res = flows.Maxflow(S, T);
if(res != sum){
cout << -1 << endl << endl;
}else{
S = s, T = t;
ll ans = flows.ver[ed].w;
flows.ver[ed].w = flows.ver[ed - 1].w = 0;
cout << ans + flows.Maxflow(S, T) << endl << endl;
}
}
return 0;
}
有源汇上下界最小流：
思路与最大流差不多，跑出可行流后，从 T 到 S 跑最大流，看能退还多少流量。答案为可行流 - 可退最大流。
【模板】：
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
template<typename T> struct Dinic{
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<T>> h;
vector<T> cur, dep;
Dinic(int n) : n(n + 1), h(n + 2) {}
void AddEdge(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
dep.assign(n, -1);
dep[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && dep[y] == -1) {
dep[y] = dep[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (T &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && dep[v] == dep[u] + 1) {
auto a = dfs(v, t, min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void reset() { // 封装退流
for (int i = 0; i < ver.size(); i += 2) {
ver[i].w += ver[i ^ 1].w;
ver[i ^ 1].w = 0;
}
}
T Maxflow(int s, int t) {
// reset();
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
void Clear(){
for(int i = 0; i <= n; i ++) h[i].clear(); // S ~ T
ver.clear();
}
};
using Flow = Dinic<ll>;
const int N = 1e5 + 10;
const ll inf = 1e18;
ll A[N], rid[N << 2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// int T; cin >> T; while(T --) solve();
int n, m, a, b; cin >> n >> m >> a >> b;
ll S = 0, T = n + 1, sum = 0;
Flow flows(n + 2);
for(int i = 1; i <= m; i ++){
int x, y, l, r; cin >> x >> y >> l >> r;
A[y] += l, A[x] -= l;
flows.AddEdge(x, y, r - l);
rid[i] = (ll)flows.ver.size() - 1;
}
for(int i = 1; i <= n; i ++){
if(A[i] > 0) flows.AddEdge(S, i, A[i]), sum += A[i];
if(A[i] < 0) flows.AddEdge(i, T, -A[i]);
}
flows.AddEdge(b, a, inf);
ll res = flows.Maxflow(S, T), ed = (ll)flows.ver.size() - 1;
if(res != sum){
cout << "please go home to sleep" << endl;
}else{
ll tot = flows.ver[ed].w;
flows.ver[ed].w = flows.ver[ed - 1].w = 0;
S = b, T = a;
cout << tot - flows.Maxflow(S, T) << endl;
}
return 0;
}
费用流：
在网络G = （V, E），每条边有容量 c(u, v)，用单位流量的费用 w(u, v)。总花费最小的最大流称为最小费用最大流，总花费最大的最大流称为最大费用最大流。
1. EK 算法：
在之前最大流用 bfs寻找一条增广路 改为 “用spfa寻找一条单位费用之和最小的增广路”。即可求出最小费用最大流。
为了退流，反向边的初始容量为 0，反向边的容量每次 + f。
为了退费，反向边的初始费用为-w, 反向边花费 + f * (- w)。
【模板1：最小费用最大流】
struct MinCostFlow {
using PII = pair<ll, ll>;
const ll INF = numeric_limits<ll>::max();
struct Edge {
int v, c, f;
Edge(int v, int c, int f) : v(v), c(c), f(f) {}
};
const int n;
vector<Edge> e;
vector<vector<int>> g;
vector<ll> h, dis;
vector<int> pre;
MinCostFlow(int n) : n(n), g(n) {}
inline void AddEdge(int u, int v, int c, int f) { // c 流量, f 费用
// if (f < 0) {
// g[u].push_back(e.size());
// e.emplace_back(v, 0, f);
// g[v].push_back(e.size());
// e.emplace_back(u, c, -f);
// } else {
g[u].push_back(e.size());
e.emplace_back(v, c, f);
g[v].push_back(e.size());
e.emplace_back(u, 0, -f);
// }
}
inline bool dijkstra(int s, int t) {
dis.assign(n, INF);
pre.assign(n, -1);
priority_queue<PII, vector<PII>, greater<PII>> que;
dis[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (dis[u] < d) continue;
for (int i : g[u]) {
auto [v, c, f] = e[i];
if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
dis[v] = d + h[u] - h[v] + f;
pre[v] = i;
que.emplace(dis[v], v);
}
}
}
return dis[t] != INF;
}
pair<int, ll> flow(int s, int t) {
int flow = 0;
ll cost = 0;
h.assign(n, 0);
while (dijkstra(s, t)) {
for (int i = 0; i < n; ++i) h[i] += dis[i];
int aug = numeric_limits<int>::max();
for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = min(aug, e[pre[i]].c);
for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
e[pre[i]].c -= aug;
e[pre[i] ^ 1].c += aug;
}
flow += aug;
cost += 1ll * (aug) * h[t];
}
return {flow, cost};
}
};
例题1：HOJ 2543 (凸费用流问题)
【题目大意】
在无向图G中，wywcgs要从源点s购买一些石头并运到汇点t。每块石头单价是 P 元。每条边i有一个初始容量Ci，当容量超过Ci时，每增加一单位容量要额外 花费Ei元。wywcgs现在手头只有C元，问他最多能买多少块石头并成功运到目 的地。（2 <= N <= 1000, 1 <= M <= 10000, 1 <= C <= 100,000,000, 1 <= P <= 10000, 0 <= Ci, Ei <= 10000）
利用每次费用流找到的都是最小费用的增广路来解题。
#include<bits/stdc++.h>
#define L(i, l, r) for(int i = l; i <= r; i ++)
#define R(i, l, r) for(int i = l; i >= r; i --)
#define ll long long
#define fi first
#define se second
#define vi vector <int>
#define vl vector <long long>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
int res;
struct MinCostFlow {
using PII = pair<ll, ll>;
const int INF = numeric_limits<int>::max();
struct Edge {
int v, c, f;
Edge(int v, int c, int f) : v(v), c(c), f(f) {}
};
const int n;
vector<Edge> e;
vector<vector<int>> g;
vector<ll> h, dis;
vector<int> pre;
MinCostFlow(int n) : n(n), g(n) {}
void AddEdge(int u, int v, int c, int f) { // c 流量, f 费用
// if (f < 0) {
// g[u].push_back(e.size());
// e.emplace_back(v, 0, f);
// g[v].push_back(e.size());
// e.emplace_back(u, c, -f);
// } else {
g[u].push_back(e.size());
e.emplace_back(v, c, f);
g[v].push_back(e.size());
e.emplace_back(u, 0, -f);
// }
}
bool dijkstra(int s, int t) {
dis.assign(n, INF);
pre.assign(n, -1);
priority_queue<PII, vector<PII>, greater<PII>> que;
dis[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (dis[u] < d) continue;
for (int i : g[u]) {
auto [v, c, f] = e[i];
if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
dis[v] = d + h[u] - h[v] + f;
pre[v] = i;
que.emplace(dis[v], v);
}
}
}
return dis[t] != INF;
}
ll flow(int s, int t, int up) {
ll flow = 0;
ll cost = 0, res = 0, rest = up;
h.assign(n, 0);
while (dijkstra(s, t)) {
for (int i = 0; i < n; ++i) h[i] += dis[i];
int aug = numeric_limits<int>::max();
for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = min(aug, e[pre[i]].c);
for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
e[pre[i]].c -= aug;
e[pre[i] ^ 1].c += aug;
}
flow = aug;
cost = 1ll * (aug) * h[t];
// 每次找到的最大的可行流，与该可行流最小费用。
if(cost <= rest){
res += flow, rest -= cost;
}else{
res += flow * rest / cost;
break;
}
}
return res;
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int Case; cin >> Case; while(Case --){
int n, m, C, P; cin >> n >> m >> C >> P;
int inf = numeric_limits<int>::max();
int S = n + 1, T = 1;
res = 0;
MinCostFlow flows(n + 2);
flows.AddEdge(S, 0, C / P, P);
for(int i = 1; i <= m; i ++){
int a, b, c, f; cin >> a >> b >> c >> f;
flows.AddEdge(a, b, c, 0);
flows.AddEdge(a, b, inf, f);
}
cout << flows.flow(S, T, C) << endl;
}
return 0;
}
【拓展：】
对于此题费用非线性，可以将费用分段建边处理。由此当我们费用函数不是线性的时候，且满足凸性。则可以分流量枚举处理。
例题2：HOJ 2715 Matrix3
【题目大意】
一个 N*N 的网格，每个单元都有一个价值 Vi 的宝物和一个高度 Hi。现在 ZhouGuyue 要作至多 K 次旅行，每次旅行如下：他可以借助bin3的直升机飞到任意一个单元，之后他每次只能向相邻的且高度比当前所在格子低的格子移动。 当他移动到一个边界的格子上时，他可以跳出这个网格并完成一次旅行。旅行中所到之处的宝物他可以全部拿走，一旦拿走原来的格子里就没有宝物了。问他最多能拿走价值多少的宝物。
【建模】
由于每个格子只有第一次经过有效，则进行拆点：将每个格子拆成两个点 $i’,i’‘$。加边 $(i’,i’‘,1,-Vi),$
（这里取负值是因为原本要求最大值，相当于取反求最大流最小值），$(i’, i’‘,inf,0)$ , $(S,i’,inf,0)$。对相邻的四个格子j，若Hi > Hj 则加边；若格子在边界则加边 (i’‘, T, inf, 0)。
之后限制增广路 <= k，求最小费用流即可。
例题3：HOJ 2739 邮政问题
【题目大意】
带权有向图上的邮路问题：一名邮递员需要经过每条有向边至少一次，最后回到出发点，一条边多次经过权值要累加，问最小总权值是多少。（2 <= N <= 100, 1 <= M <= 2000）
【建模】
首先，如果图不连通，或者入\ 出度为0则无解。
可以考虑如何计算重复边的数量：对于每个点，其出入度应该相同。
统计所有点的入度出度之差D，对于 D > 0的点，加边 (S, i, Di, 0)；对于 D > 0这样的点, 加边 (i, T, -Di, 0)；
为什么要这样做，因为考虑我们最后的可行路径每个点的出入次数一定是守恒的。假如 D > 0, 那么要多走D次这个点来让其守恒；同理，若 D < 0，则要多从这个点多走 D 次。
因为我们在所有边已经走过一遍的前提下考虑，所有从哪条边入 、出都不影响，接下来就是利用最小费用流的特性求解。
然后再对每条边 (i, j)，在网格中加边 （i，j, inf, $D_{ij}$）其中Dij为边权。
答案为最小费用流 + 原图所有边权和为结果。
【拓展】
如何求带权无向图上的问题？
若不存在欧拉回路，则必然存在偶数个奇数点，将这些奇点拉出来构建新图，任意两点之间的边权为原图中的最短距离，对新图求一次一般图最小权完美匹配。加上原图所有边权和，即为最终结果。
若进一步要求输出最小权值回路，则将每条匹配边在原图中对应的最短路上的每条边额外增加一条，这样原图便成为欧拉图，求一次欧拉回路即可。
