#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());
}
标签:ch,增广,int,ll,flow,char,dep,Dinic,模板
From: https://www.cnblogs.com/DataErr0r/p/17063083.html