【有上下界网络流】【ZOJ】2314 Reactor Cooling

【算法】有上下界网络流-无源汇(循环流)

【题解】http://www.cnblogs.com/onioncyc/p/6496532.html

//未提交

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=,maxm=,inf=0x3f3f3f3f;

struct edge{int from,v,flow;}e[maxm];

int S,T,TT,n,m,tot=,first[maxn],cur[maxn],in[maxn],d[maxn],q[],lows[maxm];

void insert(int u,int v,int w)

{

    tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].flow=;e[tot].from=first[v];first[v]=tot;

}

bool bfs()

{

    memset(d,-,sizeof(d));

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

    while(head!=tail)

     {

         int x=q[head++];if(head>)head=;

         for(int i=first[x];i;i=e[i].from)

          if(d[e[i].v]==-&&e[i].flow)

           {

               d[e[i].v]=d[x]+;

               q[tail++]=e[i].v;

               if(tail>)tail=;

          }

     }

    return d[T]!=-;

}

int dfs(int x,int a)

{

    if(x==T||a==)return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

     if(d[e[i].v]==d[x]+&&(f=dfs(e[i].v,min(a,e[i].flow)))>)

      {

          e[i].flow-=f;

          e[i^].flow+=f;

          a-=f;

          flow+=f;

          if(a==)break;

      }

    return flow;

}

int main()

{

    scanf("%d",&TT);

    while(TT--)

     {

         memset(first,,sizeof(first));

         memset(in,,sizeof(in));

         tot=;

         scanf("%d%d",&n,&m);

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

          {

              int u,v,w;

              scanf("%d%d%d%d",&u,&v,&lows[i],&w);

              in[u]-=lows[i];in[v]+=lows[i];

              insert(u,v,w-lows[i]);

         }

        S=,T=n+;

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

          {

             if(in[i]>)insert(S,i,in[i]);

             if(in[i]<)insert(i,T,-in[i]);

          }

         while(bfs())

          {

              for(int i=;i<=n+;i++)cur[i]=first[i];

            dfs(S,inf);

         }

        bool ok=;

        for(int i=first[S];i;i=e[i].from)

         if(e[i].flow)ok=;

        if(ok)

         {

             printf("YES\n");

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

              printf("%d\n",e[i^].flow+lows[i>>]);

         }

        else printf("NO\n");

     }

    return ;

}