【BZOJ1834】网络扩容

2023-10-04 16:08:58

Time Limit: 1000 ms Memory Limit: 128 MB

Description

　　给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

Input

　　输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

Output

　　输出文件一行包含两个整数，分别表示问题1和问题2的答案。

Sample Input

　　5 8 2
　　1 2 5 8
　　2 5 9 9
　　5 1 6 2
　　5 1 1 8
　　1 2 8 7
　　2 5 4 9
　　1 2 1 1
　　1 4 2 1

Sample Output

　　13 19

　　30%的数据中，N<=100
　　100%的数据中，N<=1000，M<=5000，K<=10

Solution

　　第一问直接上裸SPFA最大流，对于输入每条边$(u,v,f,c)$，流量设为输入的$f$，而费用设为0。（EK）

　　对于第二问，考虑第一问完成后的残余网络。对于残余网络上的每一条边，理应都可以0费用扩容；而残余网络上不存在的边，扩容就需要$w$（反向弧为$-w$）。

　　那么直接在第一问跑完后的残余网络上建图，对于输入的每一条边$(u,v,f,c)$，流量设为$+\infty$，费用设为$w$（反向弧$-w$）。

　　这样在两种边下跑费用流，会优先选择原来残余网络上费用为$0$的边来增广，那么0费用扩容的边刻画完成；其他的边需要付出费用的，也可以体现。

　　最后，由$n$连向一个超级汇点$T$，流量为$k$，费用为$0$，跑费用流即可。

#include <cstdio>

#include <queue>

using namespace std;

const int N=,M=,INF=;

int n,m,k,tot=,e[M][],h[N];

int S,T,dis[N],inq[N],pre[N],which[N];

struct Edge{int v,f,c,next;}g[M*];

queue<int> q;

inline void addEdge(int u,int v,int f,int c=){

    g[++tot].v=v; g[tot].f=f; g[tot].c=c; g[tot].next=h[u]; h[u]=tot;

    g[++tot].v=u; g[tot].f=; g[tot].c=-c; g[tot].next=h[v]; h[v]=tot;

}

bool spfa(){

    while(!q.empty()) q.pop();

    q.push(S);

    for(int i=;i<=T;i++) dis[i]=INF,inq[i]=pre[i]=;

    dis[S]=; inq[S]=;

    while(!q.empty()){

        int u=q.front(); q.pop();

        for(int i=h[u],v;i;i=g[i].next)

            if(g[i].f&&dis[u]+g[i].c<dis[v=g[i].v]){

                dis[v]=dis[u]+g[i].c;

                which[v]=i;

                pre[v]=u;

                if(!inq[v]){

                    inq[v]=;

                    q.push(v);

                }

            }

        inq[u]=;

    }

    return dis[T]!=INF;

}

int solve(int type){

    int mins,maxflow=,mincost=;

    while(spfa()){

        mins=INF;

        for(int u=T;u!=S;u=pre[u])

            if(g[which[u]].f<mins)

                mins=g[which[u]].f;

        maxflow+=mins; mincost+=mins*dis[T];

        for(int u=T;u!=S;u=pre[u]){

            g[which[u]].f-=mins;

            g[which[u]^].f+=mins;

        }

    }

    return !type?maxflow:mincost;

}

int main(){

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

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

        scanf("%d%d%d%d",&e[i][],&e[i][],&e[i][],&e[i][]);

        addEdge(e[i][],e[i][],e[i][]);

    }

    S=; T=n;

    printf("%d ",solve());

    T=n+;

    addEdge(n,T,k,);

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

        addEdge(e[i][],e[i][],INF,e[i][]);

    printf("%d\n",solve());

}

奇妙代码

码农公寓