8/23 网络流、最大流+hungary算法

网络流、最大流

源点S和汇点T，每条有向边的有一个权值，成为边的容量c(x,y)；若(x,y)不属于E，则c(x,y)=0； f(x,y)表示边(x,y)上的流量，c(x,y)-f(x,y)称为边的剩余容量； 最大流：从源点流向汇点的最大流量 增广路：一条从源点到汇点的所有变得剩余容量>=0得路径 残留网:由网络中所有节点和剩余容量大于0的变构成的子图； 构建反向边的目的是提供一个"退流管道",提供了"后悔机制"

P3376 【模板】网络最大流

EK()算法，复杂度为O(nmm),一般可达：n=1000,m=10000,实际所用更小

借用大佬图片： 算法流程如下

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);in>>m>>s>>t;
    for(int i=1,u,v,w;i>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    coutm;
    s=1,t=m;
    for(int i=1,u,v,w;i>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    coutm>>x;
    s=1,t=n;
    for(int i=1,u,v,w;i>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    int ans=EK();
    if(ans==0)
    {
        cout