LOJ115 无源汇有上下界可行流（上下界网络流）

　　假设初始流为每条边的下界。但这样可能流量会不守恒，我们需要在上面加上一个附加流使流量守恒。只要让每个点开始的出/入流量与原初始流相等就可以求出附加流了。那么新建超源S超汇T，令degree[i]表示流入i的边的下界之和-从i流出的边的下界之和。

　　若degree[i]>0，则表示需要有额外degree[i]的流量流入i来达到流量平衡，那么从S向i连上界为degree[i]的边。

　　若degree[i]<0，则表示需要有额外degree[i]的流量从i流出来达到流量平衡，那么从i向T连上界为-degree[i]的边。

　　跑最大流就可以求出附加流。显然maxflow<=sigma(degree[i])。如果maxflow=sigma(degree[i])，那么有可行流。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 210

#define M 50000

#define S 0

#define T 201

#define inf 1000000000

int n,m,t=-,p[N],degree[N],l[M],tot=;

int cur[N],d[N],q[N],ans=;

struct data{int to,nxt,cap,flow;

}edge[M];

void addedge(int x,int y,int z)

{

    t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=,p[x]=t;

    t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=,edge[t].flow=,p[y]=t;

}

bool bfs()

{

    memset(d,,sizeof(d));d[S]=;

    int head=,tail=;q[]=S;

    do

    {

        int x=q[++head];

        for (int i=p[x];~i;i=edge[i].nxt)

        if (d[edge[i].to]==-&&edge[i].flow<edge[i].cap)

        {

            d[edge[i].to]=d[x]+;

            q[++tail]=edge[i].to;

        }

    }while (head<tail);

    return ~d[T];

}

int work(int k,int f)

{

    if (k==T) return f;

    int used=;

    for (int i=cur[k];~i;i=edge[i].nxt)

    if (d[k]+==d[edge[i].to])

    {

        int w=work(edge[i].to,min(f-used,edge[i].cap-edge[i].flow));

        edge[i].flow+=w,edge[i^].flow-=w;

        if (edge[i].flow<edge[i].cap) cur[k]=i;

        used+=w;if (used==f) return f;

    }

    if (used==) d[k]=-;

    return used;

}

void dinic()

{

    while (bfs())

    {

        memcpy(cur,p,sizeof(p));

        ans+=work(S,inf);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("loj115.in","r",stdin);

    freopen("loj115.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read(),m=read();

    memset(p,,sizeof(p));

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read(),low=read(),high=read();

        addedge(x,y,high-low);

        degree[y]+=low,degree[x]-=low;

        l[i]=low;

    }

    for (int i=;i<=n;i++)

    if (degree[i]>) addedge(S,i,degree[i]),tot+=degree[i];

    else if (degree[i]<) addedge(i,T,-degree[i]);

    dinic();

    if (ans<tot) cout<<"NO";

    else

    {

        cout<<"YES\n";

        for (int i=;i<=m;i++)

        printf("%d\n",edge[i-<<].flow+l[i]);

    }

    return ;

}

巴特西

LOJ115 无源汇有上下界可行流（上下界网络流）

最新文章

热门文章