ZOJ 2314 Reactor Cooling

无源无汇上下界网络流裸题

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

#define N 210
#define INF 1000000000

int n,m,S,T,Ans;
struct Edge{
    int to,next;
    int value;
}edge[N*N*2];
int head[N],tot=1;
int dis[N],cur[N],Free[N],low[N*N];
queue<int> Q;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void Addedge(int u,int v,int w)
{
    tot++;edge[tot].next=head[u];edge[tot].value=w;edge[tot].to=v;head[u]=tot;
    tot++;edge[tot].next=head[v];edge[tot].value=0;edge[tot].to=u;head[v]=tot;
}

bool BFS()
{
    memset(dis,-1,sizeof(dis));
    dis[S]=0;Q.push(S);
    while(!Q.empty())
    {
        int now=Q.front();Q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]<0&&edge[i].value>0)
            {
                dis[v]=dis[now]+1;
                Q.push(v);
            }
        }
    }
    return dis[T]>0;
}

int Find(int k,int low)
{
    if(k==T)
        return low;
    int qwer;
    for(int i=cur[k];i;i=edge[i].next)
    {
        cur[k]=i;
        int v=edge[i].to;
        if(dis[v]==dis[k]+1&&edge[i].value>0&&(qwer=Find(v,min(low,edge[i].value))))
        {
            edge[i].value-=qwer;
            edge[i^1].value+=qwer;
            return qwer;
        }
    }
    return 0;
}

void Dinic()
{
    while(BFS())
    {
        for(int i=0;i<=T;i++)
            cur[i]=head[i];
        while(1)
        {
            int qwer=Find(S,INF);
            if(qwer==0)
                break;
            Ans+=qwer;
        }
    }
}

bool Pd()
{
    for(int i=head[S];i;i=edge[i].next)
    {
        if(edge[i].value)
            return false;
    }
    return true;
}

int main()
{
    int Case=read();
    while(Case--)
    {
        tot=1;
        memset(head,sizeof(head));
        memset(Free,sizeof(Free));
        n=read();m=read();
        S=0;T=n+1;
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read();low[i]=read();int z=read();
            Free[x]-=low[i];Free[y]+=low[i];
            Addedge(x,y,z-low[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(Free[i]>0)
                Addedge(S,i,Free[i]);
            else Addedge(i,-Free[i]);
        }
        Ans=0;Dinic();
        if(Pd())
        {
            printf("YESn");
            for(int i=1;i<=m;i++)
            {
                printf("%dn",edge[i*2+1].value+low[i]);
            }
        }
        else printf("NOn");
    }
    return 0;
}

（编辑：李大同）

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