网络流模板集合

#include<queue>
using namespace std;
const int M=100050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,pre[N],d[N];
struct {int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int cap)
{
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt++].cap=cap;	
}
void update(int x,int to,int flow)
{
    for(int i=x;i!=to;i=e[pre[i]^1].to)
    {
        e[pre[i]].flow+=flow;
        e[pre[i]^1].flow-=flow;	
    }	
}
int bfs(int s,int t)
{
    while (!Q.empty()) Q.pop();
    for(int i=1;i<=n;i++) d[i]=0;
    d[s]=INF,Q.push(s);
    while (!Q.empty()&&!d[t])
    {
        int x=Q.front();Q.pop();
        for(int i=head[x];~i;i=e[i].next)
        {
            int to=e[i].to;
            if (!d[to]&&e[i].flow<e[i].cap)
            {
                pre[to]=i;
                d[to]=min(d[x],e[i].cap-e[i].flow);
                Q.push(to);
            }
        }	
    }
    return d[t];
}
int EK(int s,int t)
{
    int ret=0,new_flow;
    while (new_flow=bfs(s,t))
    {
        ret+=new_flow;
        update(t,s,new_flow);
    }
    return ret;
}
int main()
{
    n=read(),m=read();
    st=read(),ed=read();
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v,read());
        add(v,u,0);
    }
    printf("%d",EK(st,ed));	
    return 0;	
}

#include<queue>
using namespace std;
const int M=120050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,d[N],cur[N];
struct {int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int cap)
{
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt++].cap=cap;	
}
int bfs(int s,int t)
{
    while (!Q.empty()) Q.pop();
    for(int i=1;i<=n;i++) d[i]=0;
    d[s]=1,Q.push(s);
    while (!Q.empty()&&!d[t])
    {
        int x=Q.front();Q.pop();
        for(int i=head[x];~i;i=e[i].next)
        {
            int to=e[i].to;
            if (e[i].flow<e[i].cap&&!d[to])
            {
                d[to]=d[x]+1;
                Q.push(to);
            }
        }	
    }
    return d[t];
}
int dfs(int x,int t,int flow)
{
    if (!flow||x==t) return flow;
    int ret=0,new_flow;
    for(int &i=cur[x];~i&&flow;i=e[i].next)
    {
        int to=e[i].to;
        if (d[x]+1==d[to])
        {
            new_flow=dfs(to,t,min(flow,e[i].cap-e[i].flow));
            e[i].flow+=new_flow;
            e[i^1].flow-=new_flow;
            ret+=new_flow;
            flow-=new_flow;		
        }		
    }
    return ret;	
}
int Dinic(int s,int t)
{
    int ret=0;
    while (bfs(s,t))
    {
    	for(int i=1;i<=n;i++) cur[i]=head[i];
        ret+=dfs(s,t,INF);
    }
    return ret;
}
int main()
{
    n=read(),m=read();
    st=read(),ed=read();
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v,read());
        add(v,u,0);
    }
    printf("%d",Dinic(st,ed));
    return 0;	
}

#include<queue>
using namespace std;
const int M=100050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,d[N],num[N],pre[N],cur[N];
struct {int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int cap)
{
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt++].cap=cap;	
}
void bfs(int s)
{
    for(int i=1;i<=n;i++) d[i]=n;
    d[s]=0,Q.push(s);
    while (!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int i=head[x];~i;i=e[i].next)
        {
            int to=e[i].to;
            if (d[x]+1<d[to]&&e[i^1].cap)
            {
                d[to]=d[x]+1;
                Q.push(to);
            }
        }	
    }
}
int update(int x,int to)
{
    int ret=INF;
    for(int i=x;i!=to;i=e[pre[i]^1].to)
        ret=min(ret,e[pre[i]].cap-e[pre[i]].flow);
    for(int i=x;i!=to;i=e[pre[i]^1].to)
    {
        e[pre[i]].flow+=ret;
        e[pre[i]^1].flow-=ret;	
    }
    return ret;
}
int ISAP(int s,int t)
{
    bfs(t);
    for(int i=1;i<=n;i++) num[d[i]]++;
    for(int i=1;i<=n;i++) cur[i]=head[i];
    int ret=0,x=s;
    while (d[s]<=n)
    {
        if (x==t) ret+=update(t,s),x=s;		
        int flag=0;
        for(int i=cur[x];~i;i=e[i].next)
        {
            int to=e[i].to;
            if (d[x]==d[to]+1&&e[i].flow<e[i].cap)
            {
                flag=1,cur[x]=i;
                pre[x=to]=i;
                break;			
            }		
        }
        if (!flag)
        {
            int idx=n-1;
            for(int i=head[x];~i;i=e[i].next)
                if (e[i].flow<e[i].cap)
                    idx=min(idx,d[e[i].to]);
            if (--num[d[x]]==0) break;
            num[d[x]=idx+1]++;
            cur[x]=head[x];
            if (x!=s) x=e[pre[x]^1].to;
        }
    }	
    return ret;
}
int main()
{
    n=read(),m=read();
    st=read(),ed=read();
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v,read());
        add(v,u,0);
    }
    printf("%d",ISAP(st,ed));
    return 0;	
}

#include<queue>
using namespace std;
const int M=50050,N=5050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,pre[N],d[N],c[N],cost=0,inq[N];
struct {int to,next,flow,cap,cost;} e[M<<1];
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int cap,int cost)
{
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].cost=cost;
    e[cnt++].cap=cap;	
}
void update(int x,int to,int flow)
{
    for(int i=x;i!=to;i=e[pre[i]^1].to)
    {
        e[pre[i]].flow+=flow;
        e[pre[i]^1].flow-=flow;	
    }	
}
int SPFA(int s,int t)
{
    for(int i=1;i<=n;i++) d[i]=INF,c[i]=0;
    d[s]=0,c[s]=INF,Q.push(s);
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop(),inq[x]=0;
        for(int i=head[x];~i;i=e[i].next)
        {
            int to=e[i].to,cost=e[i].cost;
            if (e[i].flow<e[i].cap&&d[x]+cost<d[to])
            {
            	d[to]=d[x]+cost;
                pre[to]=i;
                c[to]=min(c[x],e[i].cap-e[i].flow);
                if (!inq[to]) Q.push(to),inq[to]=1;
            }
        }	
    }
    return c[t];
}
int MCMF(int s,int t)
{
    int ret=0,new_flow;
    while (new_flow=SPFA(s,t))
    {
        ret+=new_flow;
        cost+=new_flow*d[t];
        update(t,s,new_flow);
    }
    return ret;
}
int main()
{
    n=read(),m=read();
    st=read(),ed=read();
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        int cap=read(),cost=read();
        add(u,v,cap,cost);
        add(v,u,0,-cost);
    }
    int max_flow=MCMF(st,ed);
    printf("%d %d",max_flow,cost);	
    return 0;	
}