ZOJ - 2314 Reactor Cooling 上下界可行流

题目链接点这里

虽然，以前就看过上下界这套理论，，但是一直没去过题。。今天终于补上了。。。

无源汇上下界网络流，，记录一下每个点流出去的下界流和流进来的下界流，，，如果IN>OUT,所以，，需要补上IN-OUT的自由流量才能在去掉下界之后保持流量平衡

反之，需要流掉OUT-IN的流量才能保持流量平衡

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define FIN freopen("input.txt","r",stdin)
#define fuck(x) cout<<x<<endl
const int MX=222221;
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m;
int s,t;
int head[MX],cnt;
int low[2*MX];
int IN[MX],OUT[MX];
struct Edge
{
    int nxt,to,cap;
} E[2*MX];
void edge_init()
{
    mem(head,-1);
    cnt=0;
}
void edge_add(int u,int v,int cap)
{
    E[cnt].nxt=head[u];
    E[cnt].to=v;
    E[cnt].cap=cap;
    head[u]=cnt++;
}
bool vis[MX];
int d[MX],cur[MX];
bool BFS(int s,int t)
{
    mem(vis,0);
    queue<int> Q;
    Q.push(s);
    vis[s]=1;
    d[s]=0;
    d[t]=-1;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=head[u]; ~i; i=E[i].nxt)
        {
            int v=E[i].to;
            if(vis[v]||!E[i].cap) continue;
            d[v]=d[u]+1;
            vis[v]=1;
            Q.push(v);
        }
    }
    return d[t]!=-1;
}
int DFS(int x,int t,int a)
{
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[x]; ~i; i=E[i].nxt)
    {
        int v=E[i].to;
        if(d[v]==d[x]+1&&(f=DFS(v,t,min(a,E[i].cap))))
        {
            E[i].cap-=f;
            E[i^1].cap+=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(BFS(s,t))
    {
        memcpy(cur,head,sizeof(head));
        flow+=DFS(s,INF);
    }
    return flow;
}
int main()
{
    FIN;
    int T;
    while(cin>>T)
    {
        while(T--)
        {
            edge_init();
            mem(IN,0);
            mem(OUT,0);
            scanf("%d%d",&n,&m);
            s=0;
            t=n+1;
            for(int i=0; i<m; i++)
            {
                int u,v,l,r;
                scanf("%d%d%d%d",&u,&v,&l,&r);
                low[i]=l;
                IN[v]+=l;
                OUT[u]+=l;
                edge_add(u,r-l);
                edge_add(v,u,0);
            }
            int sum=0;
            for(int i=1; i<=n; i++)
            {
                if(IN[i]>OUT[i]) edge_add(s,i,IN[i]-OUT[i]),edge_add(i,s,0),sum+=IN[i]-OUT[i];
                if(IN[i]<OUT[i]) edge_add(i,OUT[i]-IN[i]),edge_add(t,0);
            }
            if(sum==Dinic(s,t))
            {
                puts("YES");
                for(int i=0; i<m; i++)
                {
                    printf("%dn",E[2*i+1].cap+low[i]);
                }
            }
            else puts("NOn");
        }

    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!