zoj Reactor Cooling

Reactor Cooling

无源汇上下界最大流问题。

1、流量平衡。

2、满足上下界

模板题。

#include <iostream>

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 200000 + 10;

const int INF = 1 << 30;

struct Edge{

   int from,to,cap,flow;

   Edge(){};

   Edge(int _from,int _to,int _cap,int _flow)

       :from(_from),to(_to),cap(_cap),flow(_flow){};

};

vector<Edge> edges;

vector<int> G[MAXN];

int d[MAXN],cur[MAXN];

int src,sink,N,M;

bool vst[MAXN];

int b[MAXN],du[MAXN];

int sum;

void init(){

   src = N + 1; sink = src + 1;

   for(int i = 0;i <= sink;++i)

      G[i].clear();

   edges.clear();

}

void addEdge(int from,int to,int cap){

   edges.push_back(Edge(from,to,cap,0));

   edges.push_back(Edge(to,from,0,0));

   int sz = edges.size();

   G[from].push_back(sz - 2);

   G[to].push_back(sz - 1);

}

bool BFS(){

    queue<int> Q;

    memset(vst,0,sizeof(vst));

    Q.push(src);

    d[src] = 0;

    vst[src] = 1;

    while(!Q.empty()){

        int x = Q.front(); Q.pop();

        for(int i = 0;i < G[x].size();++i){

            Edge& e = edges[G[x][i]];

            if(!vst[e.to] && e.cap > e.flow){

                vst[e.to] = 1;

                d[e.to] = d[x] + 1;

                Q.push(e.to);

            }

        }

    }

    return vst[sink];

}

int DFS(int x,int a){

   if(x == sink||a == 0)

      return a;

   int flow = 0,f;

   for(int& i = cur[x];i < G[x].size();++i){

       Edge& e = edges[G[x][i]];

       if(d[e.to] == d[x] + 1 && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0){

            e.flow += f;

            edges[G[x][i]^1].flow -= f;

            flow += f;

            a -= f;

            if(a == 0) break;

       }

   }

   return flow;

}

int maxFlow(){

    int flow = 0;

    while(BFS()){

        memset(cur,0,sizeof(cur));

        flow += DFS(src,INF);

    }

    return flow;

}

void solve(){

   int flow = maxFlow();

   if(flow != sum){

      puts("NO");

      return;

   }

   puts("YES");

   for(int i = 0;i < M;++i){

      printf("%d\n",edges[i<<1].flow + b[i]);

   }

}

int main()

{

//    freopen("Input.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        init();

        int u,v,c;

        memset(du,0,sizeof(du));

        for(int i = 0;i < M;++i){

            scanf("%d%d%d%d",&u,&v,&b[i],&c);

            addEdge(u,v,c - b[i]);

            du[u] -= b[i];

            du[v] += b[i];

        }

        sum = 0;

        for(int i = 1;i <= N;++i){

            if(du[i] > 0){

                addEdge(src,i,du[i]);

                sum += du[i];

            }

            else

                addEdge(i,sink,-du[i]);

        }

        solve();

    }

    return 0;

}