本文仅仅记录做法或代码，至于标准证明等并不会出现（反正也是给自己看的qwq）

网络最大流

bool bfs(int s,int t){    for(int i=1;i<=n;++i) cur[i]=head[i];    memset(dep,0,sizeof(dep));    queue
    
      q;    q.push(s); dep[s]=1;    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(!dep[v]&&edge[i].flow)            {                dep[v]=dep[u]+1;                q.push(v);                if(v==t) return true;            }        }    }    return false;}int dfs(int s,int t,int u,int rest){    if(u==t) return rest;    int used=0;    for(int i=cur[u];i;i=edge[i].next)    {        cur[u]=i;        int v=edge[i].to;        if(dep[v]==dep[u]+1&&edge[i].flow)        {            int k=dfs(s,t,v,min(edge[i].flow,rest-used));            if(!k) dep[v]=0;            used+=k;            edge[i].flow-=k;            edge[i^1].flow+=k;        }    }    return used;}int dinic(int s,int t){    int maxflow=0,flow;    while(bfs(s,t)) while(flow=dfs(s,t,s,INF)) maxflow+=flow;    return maxflow; }
    

---

最小费用最大流

仅仅只是将bfs变为spfa，但是将原来的多路增广又打回单路增广

bool Spfa(int s,int t){    memset(dis,100,sizeof(dis));    memset(flow,100,sizeof(flow));    memset(exist,0,sizeof(exist));    queue
    
      q;    pre[t]=-1; exist[s]=1; dis[s]=0; q.push(s);    while(!q.empty())    {        int u=q.front();q.pop();exist[u]=0;        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(edge[i].flow>0&&dis[v]>dis[u]+edge[i].dis)            {                dis[v]=dis[u]+edge[i].dis;                flow[v]=min(edge[i].flow,flow[u]);                pre[v]=u;                preedge[v]=i;                if(!exist[v])                {                    exist[v]=1;                    q.push(v);                }            }        }    }    return pre[t]!=-1;}void MCMF(){    while(Spfa(s,t))    {        maxflow+=flow[t];        mincost+=flow[t]*dis[t];        int now=t;        while(now!=s)        {            edge[preedge[now]].flow-=flow[t];            edge[preedge[now]^1].flow+=flow[t];            now=pre[now];        }    }}
    

---

无源汇上下界可行流

需要保证每个点都有入度和出度才可以回环往复保证流量守恒

先将每条边流量初始赋值为下界，然后问题就是有些点不遵从流量守恒

解决方案：

建立超级源汇点S,T，对于入流量大于出流量的点i，为了使入流量=出流量，我们将S给i连一条容量为（入-出）的边，从而在不改变原图流入量的同时通过引入外资增加流出量；对于入流量小于出流量的点i，同理用i连T一条容量为（出-入）的边（可以理解为通过这条边引导入流量增加，然后删掉这个不存在的边原图就守恒了）

连边（d=入-出）

for(int i=1;i<=n;++i)    {        if(d[i]>0) ad(S,i,d[i]);        if(d[i]<0) ad(i,T,-d[i]);    }

连完边后跑最大流即可，如果从S出发的边全部满流则为有可行流，原图中每条边的反边的剩余流量即为可行流

---

有源汇上下界可行流

除了源点和汇点流量不守恒外其余点依旧守恒，然而源点出流和汇点入流相等，所以将t和s用容量INF的边连起来之后就成无源汇上下界可行流

---

上下界最大流

用无源汇上下界可行流的方法连边后从S跑最大流，得到flow1（可行流），删去S，T和其所连边，从s再跑一次最大流得到flow2（剩余流量），答案为flow1+flow2

---

上下界最小流

用上面方法得到可行流flow1之后（就可以不要了），用t向s连一条INF的边（注意是小写），然后再跑一次最大流，之前连的边的反边即为答案

dinic(S,T);    ad(t,s,INF);    dinic(S,T);    cout<
    
     <
    

上下界最小费用流

连边方法同上下界最小流，将求最大流改为求最小费用最大流

答案为每条边的下界*单价+最小费用流

AHOI2014/JSOI2014支线剧情

求从1出发的多条路径覆盖所有边至少一次的最小代价

read(n);    s=1;t=n+1;S=n+2;T=n+3;    for(int i=1;i<=n;++i)    {        read(m);        while(m--)        {            int x,t; read(x);read(t);            //单价为t            ins(i,x,1,INF,t);            ans+=t;//下界为1，所以只加t*1        }    }    for(int i=1;i<=n+1;++i)    {        if(d[i]>0) ad(S,i,d[i],0);        if(d[i]<0) ad(i,T,-d[i],0);    }    ad(t,s,INF,0);//连边跑费用流    ans+=MCMF(S,T);    cout<
    
     <