P3376 【模板】网络最大流

https://www.cnblogs.com/SYCstudio/p/7260613.html 有上面这个博客，我就不多讲了，毕竟讲的没人家好。。 dinic代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int inf=0x7fffffff; int n,m,s,t,cnt=-1; int head[300100],nxt[300100],to[300100],val[300100]; int cur[300100],dep[300100],q[3000100],w[300100]; void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } bool bfs() { memset(dep,0,sizeof(dep)); q[1]=s,dep[s]=1; int l=0,r=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(val[i] && !dep[v]) { dep[v]=dep[u]+1; q[++r]=v; } } } if(dep[t]==0) return 0; return 1; } int dfs(int u,int flow) { if(u==t) return flow; for(int& i=cur[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dep[v]==dep[u]+1 && val[i]) { int res=dfs(v,min(flow,val[i])); val[i]-=res,val[i^1]+=res; if(res) return res; } } return 0; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); addedge(y,x,0); } int ans=0; while(bfs()) { for(int i=1;i<=n;i++) cur[i]=head[i]; while(int add=dfs(s,inf)) ans+=add; } cout<<ans; return 0; } ``` 至于Edmonds-Karp、ISAP、费用流、以及一堆的概念: https://blog.csdn.net/A_Comme_Amour/article/details/79356220