/************************************************************************
网络流的定义好多呀   这里就仅仅标注定义名字吧  详细解释就交给以后的自己啦
==容量网络和网络最大流
1.容量 （容量网络，弧的容量，弧的流量)
2.网络流（可行流）—— 可行流的瞒住条件（弧流量限制条件&&平衡条件）
3.伪流
4.最大流
==链和增广路
1.饱和弧（非饱和弧）
2.零流（非零流）
3.链
4.前向弧（后向弧）
5.增广路
==残留容量和残留网络
1.残留容量（残留网络）
==割&&最小割
1.割
2.S-T割
3.割的容量（割的净流量,最小割）
￥￥最大流最小割定理

整体把关：
网络最大流的求解分两大类算法：1.增广路算法（包括一般增光路算法Ford-Filkerson算法  最短增光路算法  连续最短增广路算法） 2.预流推进算法(
         
///一般增广路算法 纯模板
#include <iostream>#include <string.h>#include <cmath>#include <stdio.h>using namespace std;#define INF 100000+10#define Max 1000struct Node{    int c; ///容量    int f;  ///流量} mapp[Max][Max];int pre[Max];  ///指明从哪个定点得到的   方便用到追踪的方法得到可改进量
int alphp[Max]; ///用来存放每点之间的可改进量int flag[Max];  ///标记该点是否已经检查过了int que[Max];  ///广搜 模拟队列int qe,qs; ///队尾  队头int v;   ///队列顶点int n,m;void Ford(){    while(1)    {        ///0是起始点        memset(pre,-1,sizeof(pre));        memset(flag,-1,sizeof(flag));        memset(alphp,-1,sizeof(alphp));        flag[0]=0;        pre[0]=0;        alphp[0]=INF;  ///之上是初始化三个数组  均标记为未使用   0点使用 0点前驱为0  0点的改进量==INF（意为0点可以流出无限多）        qs=qe=0;  ///队列扫描        que[qe]=0;  ///the begin of que[]        qe++;        while(qs<qe&&flag[n-1]==-1)        {            v=que[qs];   ///take the top of que[]            qs++;            for(int i=0; i<n; i++)            {                if(flag[i]==-1)                {
                     ///每次在改的过程  不断更新点  边；                    ///正方向未满   so改进                    if(mapp[v][i].c<INF&&mapp[v][i].f<mapp[v][i].c)                    {                        flag[i]=0;                        pre[i]=v;                        alphp[i]=min(alphp[v],mapp[v][i].c-mapp[v][i].f);                        que[qe]=i;                        qe++;                    }
                    ///反向有流量（反向流）                    else if(mapp[i][v].c<INF&&mapp[i][v].f>0)                    {                        flag[i]=0;                        pre[i]=-v;                        alphp[i]=min(alphp[v],mapp[i][v].f);                        que[qe]=i;                        qe++;                    }                }            }            flag[v]=1;        }
        ///当队列为空的时候  汇点还没有被标记 或者汇点的调整量==0   则这次失败了  跳出while循环        if(flag[n-1]==-1||alphp[n-1]==0)            break;
        ///否者就应该到追踪   更新调整了        int k1=n-1; ///最后一个点        int k2=abs(pre[k1]);  ///与最后一个点连接的点（前一个点）        int a=alphp[n-1];  ///可调整量        while(1) ///该路线一定是可调整路线        {            if(mapp[k2][k1].f<INF)  ///进行调整 在原有基础上加上调整量（更新）   正向            {                mapp[k2][k1].f+=a;            }            else   ///反向            mapp[k1][k2].f-=a;            if(k2==0) ///调整到原点了            break;            k1=k2;  //继续向前追踪            k2=abs(pre[k2]);        }    }    int maxFlow=0;  ///==最大流    for(int i=0;i<n;i++)    {        for(int j=0;j<n;j++)        {            if(i==0&&mapp[i][j].f<INF)            maxFlow+=mapp[i][j].f;            if(mapp[i][j].f<INF)            printf("%d->%d:%d\n",i,j,mapp[i][j].f);        }    }    printf("maxFlow==%d\n",maxFlow);}int main(){//   freopen("in.txt","r",stdin);    int u,v,c,f;    cin>>n>>m;    for(int i=0;i<n;i++)    {        for(int j=0;j<n;j++)        {            mapp[i][j].c=mapp[i][j].f=INF;  ///初始化        }    }    for(int i=0;i<m;i++)  ///建图    {        cin>>u>>v>>c>>f;        mapp[u][v].c=c;           mapp[u][v].f=f;    }    Ford();}

///输入输出
input:
6 10
0 1 8 2
0 2 4 3
1 3 2 2
1 4 2 2
2 1 4 2
2 3 1 1
2 4 4 0
3 4 6 0
3 5 9 3
4 5 7 2
output：
0->1:4
0->2:4
1->3:2
1->4:2
2->1:0
2->3:1
2->4:3
3->4:0
3->5:3
4->5:5
maxFlow==8

网络流模板