# 网络流:模板

# P3376 网络最大流(Dinic)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int N = 11000, M = 110000;
const int INF = 0x7fffffff;
struct node {
	int u, v, w, next;
} e[M << 1];
int cur[N], h[N], tot;
int dfn[N], ans, n, m, s, t;
void add(int u, int v, int w) {
	e[tot] = node({u, v, w, h[u]});
	cur[u] = h[u] = tot++;
}
bool bfs() {
	memset(dfn, 0, sizeof dfn);
	queue<int> q;
	dfn[s] = 1;
	q.push(s);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = h[u]; i != -1; i = e[i].next) {
			int v = e[i].v;
			if(e[i].w and !dfn[v]) {
				dfn[v] = dfn[u] + 1;
				q.push(v);
				if(v == t) return true;
			}
		}
	}
	return false;
}
int dfs(int u, int low) {
	if(u == t) return low;
	int w = low;
	for(int i = cur[u]; i != -1; i = e[i].next) {
		int v = e[i].v;
		cur[u] = i;
		if(e[i].w and dfn[v] == dfn[u] + 1) {
			int f = dfs(v, min(w, e[i].w));
			e[i].w -= f; e[i^1].w += f;
			w -= f;
			if(!w) break;
		}
	}
	return low - w;
}
void dinic() {
	while(bfs()) {
		memcpy(cur, h, sizeof cur);
		ans += dfs(s, INF);
	}
}
int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	memset(h, -1, sizeof h);
	for(int i=1, u, v, w; i<=m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
		add(v, u, 0);
	}
	dinic();
	printf("%d\n", ans);
	return 0;
}

# P3381 最小费用最大流(单路增广)

# Dijkstra

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline
const int N = 5500, M = 55000, INF = 0x3f3f3f3f;
struct point {
    int u, val;
    point(int _u = 0, int _val = 0): u(_u), val(_val) {}
    bool operator < (const point &o) const { return val > o.val; } 
};
priority_queue <point> q;
struct node {
    int u, v, w, f, next;
    node() {}
} e[M << 1];
int head[N], tot = 0;
il void add(int u, int v, int w, int f) {
    e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].f = f;
    e[tot].next = head[u]; head[u] = tot++;
}
int h[N], dis[N], flow[N], pre[N];
int n, m, s, t;
int maxflow = 0, mincost = 0;
il bool dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    memset(pre, -1, sizeof pre);
    
    dis[s] = 0;
    q.push(point(s, 0));
    while (!q.empty()) {
        int u = q.top().u, val = q.top().val;
        q.pop();
        if (val > dis[u]) continue;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w and dis[v] > dis[u] + e[i].f + h[u] - h[v]) {
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                dis[v] = dis[u] + e[i].f + h[u] - h[v];
                q.push(point(v, dis[v]));
            }
        }
    }
    return dis[t] != INF;
}
il void check() {
    
    for (int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    maxflow += flow[t];
    mincost += (dis[t] - h[s] + h[t]) * flow[t];
    
    for(int i=1; i<=n; ++i) h[i] += dis[i];
}
int main() {
    
    memset(head, -1, sizeof head);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while (dijkstra()) check();
    printf("%d %d\n", maxflow, mincost);
    
    return 0;
}

# SPFA

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int N = 5500, M = 110000, INF = 0x3f3f3f3f;
struct node {
    int u, v, w, f, next;
} e[M];
int h[N], tot = 0;
void add(int u, int v, int w, int f) {
    e[tot] = {u, v, w, f, h[u]};
    h[u] = tot++;
}
int pre[N], flow[N], dis[N];
bool vis[N];
int n, m, s, t, maxflow, mincost;
bool spfa() {
    
    memset(pre, -1, sizeof pre);
    memset(vis, false, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dis[s] = 0;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and dis[v] > dis[u] + e[i].f) {
                dis[v] = dis[u] + e[i].f;
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    
    return dis[t] != INF;
}
void check() {
    for(int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    
    mincost += dis[t] * flow[t];
    maxflow += flow[t];
}
int main() {
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    memset(h, -1, sizeof h); 
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while(spfa()) check();
    
    printf("%d %d\n", maxflow, mincost);
    return 0;
}

# LOJ115 无源汇有上下界可行流(超级源汇)

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline
const int N = 220, M = 11000, INF = 0x3f3f3f3f;
struct node {
    int u, v, w, next;
} e[M * 6];
int head[N], cur[N], tot = 0;
il void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
}
int h[N], n, m, ss, tt;
il bool bfs() { // 分层 
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    queue<int> q;
    q.push(ss);
    h[ss] = 1;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == tt) return true;
                q.push(v);
            }
        }
    }
    return false;
}
int dfs(int u, int low) {
    if(u == tt) return low;
    int w = low;
    for(int i = cur[u]; i != -1; i = e[i].next, cur[u] = i) {
        int v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w));
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}
int tflow = 0, sflow = 0;
il void dinic() {
    
    for(int i = head[ss]; i != -1; i = e[i].next)
        sflow += e[i].w; // 出流量 
        
    while(bfs()) dfs(ss, INF);
    
    for(int i = head[tt]; i != -1; i = e[i].next) 
        tflow += e[i].w; // 入流量 
    
    if(sflow == tflow) { // 满流 
        printf("YES\n");
        for(int i=0; i<tot; i+=6) 
            printf("%d\n", e[i+1].w + e[i+5].w); // 反边流量和 
    } else printf("NO\n");
    
}
int main() {
    
    freopen("loj115.in", "r", stdin);
    
    scanf("%d%d", &n, &m);
    
    memset(head, -1, sizeof head);
    ss = 0, tt = n+1;
    for(int i=1, u, v, l, h; i<=m; ++i) { // 建图 
        scanf("%d%d%d%d", &u, &v, &l, &h);
        add(u, tt, l);
        add(tt, u, 0);
        add(ss, v, l);
        add(v, ss, 0);
        add(u, v, h-l);
        add(v, u, 0);
    }
    
    dinic();
    
    return 0;
}

# 有源汇有上下界(转无源汇,然后断边)

# 最大流(顺流增广)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int N = 220, M = 22000, INF = 0x3f3f3f3f;
struct node {
	int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
	e[tot] = (node) {u, v, w, head[u]};
	head[u] = tot++;
	e[tot] = (node) {v, u, 0, head[v]};
	head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
	
	memset(h, 0, sizeof h);
	memcpy(cur, head, sizeof cur);
	
	queue<int> q;
	q.push(s);
	h[s] = 1;
	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = head[u], v; i != -1; i = e[i].next) {
			v = e[i].v;
			if(e[i].w and !h[v]) {
				h[v] = h[u] + 1;
				if(v == t) return true;
				q.push(v); 
			}
		}
	}
	return false;
}
int dfs(int u, int low, int t) {
	if(u == t) return low;
	
	int w = low;
	for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
		v = e[i].v;
		if(e[i].w and h[v] == h[u] + 1) {
			int f = dfs(v, min(w, e[i].w), t);
			e[i].w -= f;
			e[i^1].w += f;
			w -= f;
			if(!w) break;
		}
	}
	return low - w;
}
int main() {
	
	//freopen("loj116.in", "r", stdin);
	
	scanf("%d%d%d%d", &n, &m, &s, &t);
	
	ss = 0, tt = n+1;
	memset(head, -1, sizeof head);
	for(int i=1, u, v, l, h; i<=m; ++i) {
		scanf("%d%d%d%d", &u, &v, &l, &h);
		in[u] -= l; in[v] += l;
		add(u, v, h-l);
	}
	
	for(int i=1; i<=n; ++i) {
		if(!in[i]);
		else if(in[i] > 0) {
			sflow += in[i];
			add(ss, i, in[i]);
		} else {
			add(i, tt, -in[i]);
		}
	}
	
	add(t, s, INF);
	
	while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
	
	if(sflow != tflow) {
		printf("please go home to sleep\n");
		return 0;
	}
	
	for(int i = head[ss]; i != -1; i = e[i].next) 
		e[i].w = e[i^1].w = 0;
	
	for(int i = head[tt]; i != -1; i = e[i].next)
		e[i].w = e[i^1].w = 0;
	
	int sum = e[--tot].w;
	e[tot-1].w = e[tot].w = 0;
	
	while(bfs(s, t)) sum += dfs(s, INF, t);
	
	printf("%d\n", sum);
		
	return 0;
}

# 最小流(逆流增广)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int N = 220, M = 22000, INF = 0x3f3f3f3f;
struct node {
	int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
	e[tot] = (node) {u, v, w, head[u]};
	head[u] = tot++;
	e[tot] = (node) {v, u, 0, head[v]};
	head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
	
	memset(h, 0, sizeof h);
	memcpy(cur, head, sizeof cur);
	
	queue<int> q;
	q.push(s);
	h[s] = 1;
	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = head[u], v; i != -1; i = e[i].next) {
			v = e[i].v;
			if(e[i].w and !h[v]) {
				h[v] = h[u] + 1;
				if(v == t) return true;
				q.push(v); 
			}
		}
	}
	return false;
}
int dfs(int u, int low, int t) {
	if(u == t) return low;
	
	int w = low;
	for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
		v = e[i].v;
		if(e[i].w and h[v] == h[u] + 1) {
			int f = dfs(v, min(w, e[i].w), t);
			e[i].w -= f;
			e[i^1].w += f;
			w -= f;
			if(!w) break;
		}
	}
	return low - w;
}
int main() {
	
	//freopen("loj116.in", "r", stdin);
	
	scanf("%d%d%d%d", &n, &m, &s, &t);
	
	ss = 0, tt = n+1;
	memset(head, -1, sizeof head);
	for(int i=1, u, v, l, h; i<=m; ++i) {
		scanf("%d%d%d%d", &u, &v, &l, &h);
		in[u] -= l; in[v] += l;
		add(u, v, h-l);
	}
	
	for(int i=1; i<=n; ++i) {
		if(!in[i]);
		else if(in[i] > 0) {
			sflow += in[i];
			add(ss, i, in[i]);
		} else {
			add(i, tt, -in[i]);
		}
	}
	
	add(t, s, INF);
	
	while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
	
	if(sflow != tflow) {
		printf("please go home to sleep\n");
		return 0;
	}
	
	for(int i = head[ss]; i != -1; i = e[i].next) 
		e[i].w = e[i^1].w = 0;
	
	for(int i = head[tt]; i != -1; i = e[i].next)
		e[i].w = e[i^1].w = 0;
	
	int sum = e[--tot].w;
	e[tot-1].w = e[tot].w = 0;
	
	while(bfs(s, t)) sum += dfs(s, INF, t);
	
	printf("%d\n", sum);
		
	return 0;
}
更新于