CSP201812-05 管道清洁

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)


题解

我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题,然后就这个题爆零了

实际上我已经想明白是上下界的费用流了,但是并不会有上下界的情况,所以只能想各种奇技淫巧。

所以,此题的正解就是无源汇有上下界的最小费用可行流。

对于无源汇的网络流问题,我们通常会设置虚拟源点S和虚拟汇点T。然后再在图上进行构建。

对于这个题也是一样,只是因为有上下界所以我们需要对图进行一下改进。

我们考虑一条边一定会流下界那么多的流,这样整张图的残量网络就构成了一个流量不平衡的图。我们需要构建另外一张流量不平衡的图,使得原始图和我们构建的图互补成为一张流量平衡的图。

我们考虑对于原图中进行统计,一个点每流出1流量,度数du[x]-1,流入1流量,度数du[x]+1。

如果最终一个点的度数<0(流出大于流入),则其在互补图中流入就要大于流出,这样我们就需要给他添加一些流出渠道来疏通这些多余的流入流量,这样就从点x向虚拟汇点T连一条容量为-du[x]的边。反之同理。

如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的与原图互补的附加流。

那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的S-T最大流,所以跑S到T的最大流即可.如果最大流的大小等于S出发的所有边的流量上限之和(此时指向T的边也一定满流,因为这两部分边的流量上限之和相等),则说明此图是有可行流的.

在此题中也是如此,只是原图上的边加上了费用而已,而新加的边费用为0,直接跑有上下界最大费用可行流即可。

代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
    int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr = v;e[cnt].to = u;e[cnt].cap = 0;e[cnt].dis = -d;e[cnt].next = h[v];h[v] = cnt++;
    return;
}
int pre[maxn],d[maxn],vis[maxn];
int du[maxn];
int n,m;
int u,v,w;
int precost = 0;
int sum = 0;
char type;
bool SPFA(int s,int t){
    for(int i = s;i <= t;++i){
        pre[i] = -1;
        d[i] = INF;
        vis[i] = 0;
    }
    queue<int>q;
    q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            int to = e[i].to;
            if(d[to] > d[now] + e[i].dis && e[i].cap > 0){
                pre[to] = i;
                d[to] = d[now] + e[i].dis;
                if(!vis[to]){
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    return pre[t] != -1;
}
int mcmf(int s,int t){
    int cost = 0,flow = 0;
    while(SPFA(s,t)){
        int f = INF;
        for(int i = pre[t];i != -1;i = pre[e[i].fr]){
            f = min(f,e[i].cap);
        }
        flow += f;
        cost += f * d[t];
        for(int i = pre[t];i != -1;i = pre[e[i].fr]){
            e[i].cap -= f;
            e[i^1].cap += f;
        }
    }
    if(sum != flow)return -1;
    return cost + precost;
}
int main(){
    scanf("%d %d %d",&T,&S,&E);
    while(T--){
        scanf("%d %d",&n,&m);
        for(int i = 0;i <= n+1;++i)h[i] = -1,du[i] = 0;
        cnt = 0;precost = 0;
        for(int i = 1;i <= m;++i){
            scanf("%d %d %c",&u,&v,&type);
            if(type == 'A'){
                add(u,v,INF,E);
                du[u]--;
                du[v]++;
                precost += E;
            }
            else if(type == 'B'){
                du[u]--;
                du[v]++;
                precost += E;
            }
            else if(type == 'C'){
                add(u,v,INF,E);
            }
            else add(u,v,1,E);
        }
        int s = 0,t = n + 1;
        sum = 0;
        for(int i = 1;i <= n;++i){
            if(du[i] > 0){
                sum += du[i];
                add(s,i,du[i],0); 
            }
            else{
                add(i,t,-du[i],0);
            }
        }
        int ans = mcmf(s,t);
        printf("%d\n",ans);
    }
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00