SGU 194 Reactor Cooling 有上下界的网络流 网络流拆点

无源汇有上下界限制网络流

拆点可解

设超级源点 ss 和超级汇点 tt

deg[i] = i 点的流入容量和 - i 点的流出容量和

若 deg[i] > 0 建立 ss -> i 边权为 deg[i] 的边 强行流出 deg[i] 的流量

若 deg[i] < 0 建立 i -> tt 边权为 -deg[i] 的边 强行流入 -deg[i] 的流量

贴代码（AC，15ms）

#include<iostream>
#include<queue>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF = 0x7ffffff;
const int MAXN = 205;
const int MAXM = MAXN * MAXN;
int n,m,s,t,cnt;
bool vis[MAXN];
int head[MAXN],deg[MAXM],dl[MAXM];
int d[MAXN],cur[MAXN],que[MAXN];
struct edge_{
    int from,to,cap,flow,next;
}edge[MAXM];

void init(){
    memset(head,-1,sizeof(head));
    memset(edge,sizeof(edge));
    memset(deg,sizeof(deg));
    cnt = 0;
}

void add(int from,int to,int cap){
    edge[cnt].from = from,edge[cnt].to = to;
    edge[cnt].cap = cap,edge[cnt].next = head[from];
    edge[cnt].flow = 0;
    head[from] = cnt++;
    edge[cnt].from = to,edge[cnt].to = from;
    edge[cnt].cap = 0,edge[cnt].next = head[to];
    edge[cnt].flow = 0;
    head[to] = cnt++;
}

bool bfs(){
    memset(vis,false,sizeof(vis));
    memset(d,sizeof(d));
    d[s] = 0,vis[s] = 1,que[0] = s;
    int tail = 0,front = 1;
    while(tail < front){
        int x = que[tail++];
        for(int now = head[x]; ~now; now = edge[now].next){
            edge_ &e = edge[now];
            if(!vis[e.to] && e.cap > e.flow){
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                que[front++] = e.to;
            }
        }
    }
    return vis[t];
}

int dfs(int x,int a){
    if(x == t || a == 0)
        return a;
    int flow = 0,f;
    for(int &now = cur[x]; ~now; now = edge[now].next){
        edge_ &e = edge[now];
        if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow))) > 0){
            e.flow +=f;
            edge[now ^ 1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0)
                break;
        }
    }
    return flow;
}

int maxFlow(int _s,int _t,int _n,int _m){
    s = _s,t = _t;
    n = _n,m = _m;
    int flow = 0;
    while(bfs()){
        for(int i = 1; i <= n; i++)
            cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

int main(){
    int n,l,r,ss,tt;
    while(~scanf("%d%d",&n,&m)){
        init();
        ss = n + 1,tt = n + 2;
        for(int i = 1; i <= m; ++i){
            scanf("%d%d%d%d",&s,&t,&l,&r);
            deg[s] -= l,deg[t] += l,dl[i] = l;
            add(s,r - l);
        }
        int sum = 0;
        for(int i = 1; i <= n; ++i){
            if(deg[i] > 0){
                add(ss,i,deg[i]);
                sum += deg[i];
            }
            else
                add(i,tt,-deg[i]);
        }
        if(maxFlow(ss,n + 2,m) == sum){
            printf("YESn");
            for(int i = 0; i < m; ++i)
                printf("%dn",edge[i * 2].flow + dl[i + 1]);
        }
        else{
            printf("NOn");
        }
    }
    return 0;
}

（编辑：李大同）

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