dinic 网络流模板

dinic的复杂度为n^2*m,n是点，m是边。要注意指定起点和终点，先分层，然后进行dfs。 //密集图 const int maxn = 240; int cap[maxn][maxn]; int layer[maxn]; int st, en;//start point, end point bool count_layer() { queue<int> q; q.push(st); memset(layer, -1, sizeof(layer)); layer[st] = 0; while(!q.empty()) { int v = q.front(); q.pop(); for(int i = st; i <= en; i++) { if(layer[i] == -1 && cap[v][i] > 0) { layer[i] = layer[v]+1; if(i == en) return true; q.push(i); } } } return false; } int dfs(int root, int cur_flow) { int dt = cur_flow;//the rest of cur_flow if (root == en) return dt; for (int i = 0; i <= en; i++) { if (cap[root][i] > 0 && layer[i] == layer[root]+1) { int flow = dfs(i, min(dt, cap[root][i])); cap[root][i] -= flow; cap[i][root] += flow; dt -= flow; } } return cur_flow - dt; } int dinic() { int ans = 0; while(count_layer()) ans += dfs(st, INF); return ans; }