【模板】网络最大流 Dinic（多路增广+当前弧优化）

复杂度上界为 \(\Theta(n^2m)\)，实际效率远高于此。
#include <bits/stdc++.h>

using namespace std;

const int N=5e5+5;

const int M=1e6+5;

const int MN=1e3+5;

typedef long long ll;

inline int read(){int x(0), f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return f?-x:x;}

template <typename T> void read(T &x){x=0; T f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x;}

template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){read(x);read(arg...);}

template <typename T> inline void write(T x){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot);}

template <typename T> void write(T x,char c){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot); putchar(c);}

void Solve();

struct Graph{

    int to, next;

    ll w;

}G[M << 1];

int _head[N], cur[N], cnt(1);

void addEdge(int u,int v,int w = 1){G[++cnt] = (Graph){v, _head[u], w}; _head[u] = cnt;}

int n,m,s,t;

int main(){

//    Multicase()

        Solve();

}

int dep[N],que[N];

bool bfs(){

	memcpy(cur + 1, _head + 1, (n + 5) * sizeof(cur[0]));

	memset(dep, 0, (n + 5) * sizeof(dep[0]));

	dep[s] = 1;

	int head = 1, tail = 0; que[++tail] = s;

	while(tail >= head){

		int u = que[head++];

		for(int i = _head[u]; i; i = G[i].next){

			int t = G[i].to;

			if(G[i].w && !dep[t]){

				dep[t] = dep[u] + 1;

				que[++tail] = t;

			}

		}

	}

	return dep[t];

}

ll dfs(int now, ll flow){

	ll tot = 0, f = 0;

	if(now == t || flow == 0) return flow;

	for(int i = cur[now]; i; i = G[i].next){

		cur[now] = i;

		int t = G[i].to;

		if(G[i].w && dep[t] == dep[now] + 1){

			if(f = dfs(t, min(flow, G[i].w))){

				G[i].w -= f;

				G[i ^ 1].w += f;

				tot += f;

				flow -= f;

				if(flow == 0) break;

			}

		}

	}

	return tot;

}

ll dinic(){

	ll maxflow = 0;

	while(bfs()) maxflow += dfs(s, 1<<30);

	return maxflow;

}

void Solve(){

	read(n, m);

	s = 1, t = n;

	for(int i = 1; i <= m; i++){

		int u, v, w;

		read(u, v, w);

		addEdge(u, v, w);

		addEdge(v, u, 0);

	}

	printf("%lld\n", dinic());

}
巴特西

【模板】网络最大流 Dinic（多路增广+当前弧优化）

最新文章

热门文章
