网络流指的是：网络流(network-flows)是一种类比水流的解决问题方法。（类似于水管群，有一个源点（水无限多），和一个汇点，最大流就代表这个点水管群（边集）每秒最大能送道汇点的水量）
这个怎么求，首先是枚举从原点能到汇点的路径，然后找到这个路径边权的最小值，这个路劲的每条边减去这个值，大概这个样子
（借用同校某大佬的图）
但是明显没给我反悔的机会嘛，万一我不想这样做，岂不没地方反悔了
~Point 1 反边~
这东西就是类似于给你一个反悔的机会的，因为反向图建过去的丑的一批的路径等价于每个单独路径
原理：正向边减去当前流量，反向边加上当前流量。
比如这张图中，有一个产地，要运货给销地（也就是6号点），问如何才能给销地运输最多货物（图片是学校ppt的）
显然这张图就没有刚才那张好办，因此我们加入反边这一个概念
问什么加入反边呢，先给你看这会在哪个加了反边的图（蓝色为反边边权）
（该运输方案表示：2吨产品沿有向路P1（1，2，4，6）运到销地；1吨产品沿有向路P2（1，2，5，6）运到销地；2吨产品沿有向路P3（1，3，5，6）运到销地。）
现在我们又找到一条P4（1,2,3,4,6）的路径。
Level 1.P3376 【模板】网络最大流
就是一个裸题……
由于这个代码是第一次掌握，有些东西还不能完全化为自己的理解，故有些地方传承了教练给的代码的格式，这些东西我会在里面说明的
但是作为入门内容，还是打一下。我的注释应该会给的很清楚吧
#include<iostream>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<algorithm> using namespace std; int n,m,st,ed,size,ans,ct[],head[],dep[],vis[]; struct edge{
int next,to,dis,start;
}e[]; void addedge(int next,int to,int dis)
{
e[size].to=to;
e[size].dis=dis;
e[size].next=head[next];
e[size].start=next; //这个貌似没什么用
head[next]=size;
size++; //还有另一种写法，详见下面addedge
} void addedge(int next,int to,int dis)
{
e[++size].dis=dis; //这种写法可以先令size=1，这样 边就从2开始存了，也能满足异或1是反向边
e[size].to=to; //或者令size =-1 和就和上面写法差不多
e[size].next=head[next];
head[next]=size;
} int bfs()
{
queue <int> q;
memset(dep,,sizeof(dep));
memset(vis,,sizeof(vis));
q.push(st);
vis[st]=;
while(!q.empty())
{
int t=q.front();
q.pop();
int i,j,k;
for(i=head[t];i!=-;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(k>&&!dep[j]&&!vis[j]) //dep类似于图的深度，把网络流看作水流，防止回流
{
dep[j]=dep[t]+;
q.push(j);
vis[j]=;
}
}
}
return vis[ed]; //如果终点还能被增广就就返回1
} int dfs(int t,int nowwater)
{
if(t==ed||!nowwater) return nowwater; //1.到终点返回答案，2.走不通返回0
int tot=;
for(int &i=ct[t];i!=-;i=e[i].next) //当前弧优化，防止无用寻找
{
int j=e[i].to;
int &k=e[i].dis; //暂时不知道这个&有什么意思，但是去掉也可以过
if(k>&&dep[j]==dep[t]+)
{
int f=dfs(j,min(k,nowwater-tot));
e[i].dis-=f;
e[i^].dis+=f; //异或1让二进制最后一位变化 比如1001001 ^1 ==1001000 刚好指向另一条边
tot+=f;
if(nowwater==tot) return tot;
}
}
return tot; //当前能流到终点的最大水量
} void dinic()
{
while(bfs())
{
for(int i=;i<=n;i++)
{
ct[i]=head[i];
}
ans+=dfs(st,0x3f3f3f3f); //初始值一定设为最大值
}
} int main()
{
int i,j;
scanf("%d %d %d %d",&n,&m,&st,&ed);
memset(head,-,sizeof(head));
for(i=;i<=m;i++)
{
int t1,t2,t3;
scanf("%d %d %d",&t1,&t2,&t3); //建边建正向边和反向边
addedge(t1,t2,t3);
addedge(t2,t1,);
}
dinic();
printf("%d",ans);
return ;
}
时间复杂度O(可以过)