(模板) Dinic 最大流

谁借莪１个温暖的怀抱￠ 2022-04-25 02:34 170阅读 0赞

# 代码 #

/* * DINIC 模板 * * BEGIN */
    
    /* 需要的头文件 #include <string.h> #include <queue> #include <vector> using namespace std; */
    
    #define MAXN 10000 // 结点最大数量
    #define INF 0x7fffffff
    
    typedef struct { 
    	int from;
    	int to;
    	int flow;
    	int capacity;
    } Edge;
    
    int nNode, nEdge; // 结点个数, 边的个数
    vector<Edge> edges; // 边的数组 (正向反向边相邻)
    vector<int> adj[MAXN]; // 邻接表 (存储的是边的ID)
    int level[MAXN];
    int src, dst; // 源点, 汇点
    
    int min(int a, int b) { return (a < b) ? a : b;}
    
    void init() { 
    	for (int i = 0; i < nNode; i++) adj[i].clear();
    	edges.clear();
    }
    
    // 添加边
    void addEdge(int from, int to, int capacity) { 
    	edges.push_back((Edge){ from, to, 0, capacity});
    	edges.push_back((Edge){ to, from, 0, 0});
    	int sz = edges.size();
    	adj[from].push_back(sz-2);
    	adj[to].push_back(sz-1);
    }
    
    bool dinic_bfs() { 
    	queue<int> Q;
    	memset(level, 0, sizeof(level));
    	Q.push(src);
    	level[src] = 1;
    	while (!Q.empty()) { 
    		int node = Q.front();
    		Q.pop();
    		for (int i = 0; i < adj[node].size(); i++) { 
    			Edge e = edges[adj[node][i]];
    			int next = e.to;
    			if (level[next] || e.capacity <= e.flow) continue;
    			level[next] = level[node] + 1;
    			Q.push(next);
    		}
    	}
    	return level[dst] != 0;
    }
    
    int dinic_dfs(int node, int flow) { 
    	if (node == dst) return flow;
    	int temp = flow;
    	for (int i = 0; i < adj[node].size(); i++) { 
    		int eid = adj[node][i];
    		Edge e = edges[eid];
    		int next = e.to;
    		if (level[next] != level[node]+1 || e.capacity <= e.flow) continue;
    		int t = dinic_dfs(next, min(temp, e.capacity - e.flow));
    		edges[eid].flow += t;
    		edges[eid^1].flow -= t;
    		temp -= t;
    		if (!temp) break;
    	}
    	return flow - temp;
    }
    
    // 返回最大流
    int dinic() { 
    	int result = 0;
    	int flow = 0;
    	while (dinic_bfs()) 
    		while ((flow = dinic_dfs(src, INF)))
    			result += flow;
    	return result;
    }
    
    /* * END */

# 用法 #

#include <stdio.h>
    #include <string.h>
    #include <queue>
    #include <vector>
    using namespace std;
    /* 此处粘贴上述代码 */
    
    int main() { 
    	scanf("%d%d%d%d", &nNode, &nEdge, &src, &dst);
    	src--; // 如果题目的结点ID从1开始, 那么就需要减一
    	dst--; // 同上
    	for (int i = 0; i < nEdge; i++) { 
    		int from, to, capacity;
    		scanf("%d%d%d", &from, &to, &capacity);
    		addEdge(from-1, to-1, capacity); // 同上
    	}
    	printf("%d\n", dinic());
    }