【洛谷 - P3376 】【模板】网络最大流

题干：

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入输出格式

输入格式：

 

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）

 

输出格式：

 

一行，包含一个正整数，即为该网络的最大流。

 

输入输出样例

输入样例#1： 复制

4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40

输出样例#1： 复制

50

解题报告：

   RT。

AC代码：

#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> using namespace std; int n,m; int tot; struct Edge {int to,ne,w; } e[100005 * 2]; int head[10005]; int st,ed; int dis[10050],q[10005];//一共多少个点跑bfs，dis数组和q数组就开多大。 void add(int u,int v,int w) {e[++tot].to=v;e[tot].w=w;e[tot].ne=head[u];head[u]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } int dfs(int cur,int f) {if(cur==ed) return f;int w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=f-flow;w=dfs(e[i].to,min(w,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;if(flow==f) return f;} }if(!flow) dis[cur]=-1;return flow; } int dinic() {int ans = 0;while(bfs(st,ed)) ans+=dfs(st,0x7fffffff);return ans; } int main() {cin>>n>>m>>st>>ed;tot=1;for(int i = 1; i<=n; i++) head[i] = -1;for(int a,b,c,i = 1; i<=m; i++) {scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,0);} printf("%d\n",dinic()); return 0; }

得出结论：如果是^1的话，那就必须tot=1，然后存边的时候++tot这样。

但是要是i和i+1的话，那就tot=1或者tot=2都可以了。

总结

以上是生活随笔为你收集整理的【洛谷 - P3376 】【模板】网络最大流的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。