P2604 [ZJOI2010]网络扩容最小费用最大流

左手的ㄟ右手 2021-12-13 13:03 240阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

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

输出格式：

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

## 输入输出样例 ##

输入样例\#1：  复制

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

输出样例\#1：  复制

13 19
    
    
    
    第一问很简单 跑一遍最大流
    然后再加上给每条边加上k容量的花费流   再给n-n+1 加上容量为maxflow+k的容量流
    
    建议全部重建图

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    //input by bxd
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define repp(i,a,b) for(int i=(a);i>=(b);--i)
    #define RI(n) scanf("%d",&(n))
    #define RII(n,m) scanf("%d%d",&n,&m)
    #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
    #define RS(s) scanf("%s",s);
    #define ll long long
    #define pb push_back
    #define inf 0x3f3f3f3f
    #define CLR(A,v)  memset(A,v,sizeof A)
    //
    const int N=1000001;
    
    int n,m,S,T,maxflow,mincost,last[N],pre[N],dis[N],flow[N];
    bool vis[N];
    struct Edge{
        int next,to,flow,dis;
    }edge[N<<1];
    int pos=1,head[N];
    void init()
    {
        pos=1;
        CLR(head,0);
        mincost=maxflow=0;
    }
    queue <int> q;
    int id(int x,int y) {
           return n*(x-1)+y;}
    
    void add(int from,int to,int flow,int dis)//flow流量 dis费用
    {
        edge[++pos].next=head[from];
        edge[pos].flow=flow;
        edge[pos].dis=dis;
        edge[pos].to=to;
        head[from]=pos;
        edge[++pos].next=head[to];
        edge[pos].flow=0;
        edge[pos].dis=-dis;
        edge[pos].to=from;
        head[to]=pos;
    }
    bool spfa(int s,int t)
    {
        CLR(dis,0x3f);
        CLR(flow,0x3f);
        CLR(vis,0);
        while (!q.empty()) q.pop();
        dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
        int tot=0;
        while (!q.empty())
        {
            int now=q.front(); q.pop(); vis[now]=0;
            for (int i=head[now]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
                {
                    dis[to]=edge[i].dis+dis[now];
                    flow[to]=min(edge[i].flow,flow[now]);
                    last[to]=i;
                    pre[to]=now;
                    if (!vis[to])
                    {
                        q.push(to); vis[to]=1;
                    }
                }
            }
        }
        return pre[t]!=-1;
    }
    void MCMF(int s,int t)
    {
        while (spfa(s,t))
        {
            int now=t;
            maxflow+=flow[t];
            mincost+=flow[t]*dis[t];
            while (now!=s)
            {
                edge[last[now]].flow-=flow[t];//dis . flow
                edge[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
    }
    struct node
    {
        int u,v,flow,cost;
    }node[N];
    int s,t,k;
    
    int main()
    {
        RIII(n,m,k);
        rep(i,1,m)
        {
            int x;RII(node[i].u,node[i].v);RII(node[i].flow,node[i].cost);
            add(node[i].u,node[i].v,node[i].flow,0);
        }
        MCMF(1,n);
        cout<<maxflow;
        int temp=maxflow+k;//记录最大流
    
        init();
        add(n,n+1,temp,0);
        rep(i,1,m)
        {
            add(node[i].u,node[i].v,k,node[i].cost);
            add(node[i].u,node[i].v,node[i].flow,0);
        }
        MCMF(1,n+1);
        printf(" %d",mincost);
       // printf(" %d",maxflow);
        return 0;
    }

不全部重建图的话

给n-n+1 加上容量为k的容量流！！！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    //input by bxd
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define repp(i,a,b) for(int i=(a);i>=(b);--i)
    #define RI(n) scanf("%d",&(n))
    #define RII(n,m) scanf("%d%d",&n,&m)
    #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
    #define RS(s) scanf("%s",s);
    #define ll long long
    #define pb push_back
    #define inf 0x3f3f3f3f
    #define CLR(A,v)  memset(A,v,sizeof A)
    //
    const int N=1000001;
    
    int n,m,S,T,maxflow,mincost,last[N],pre[N],dis[N],flow[N];
    bool vis[N];
    struct Edge{
        int next,to,flow,dis;
    }edge[N<<1];
    int pos=1,head[N];
    void init()
    {
        pos=1;
        CLR(head,0);
        mincost=maxflow=0;
    }
    queue <int> q;
    int id(int x,int y) {
           return n*(x-1)+y;}
    
    void add(int from,int to,int flow,int dis)//flow流量 dis费用
    {
        edge[++pos].next=head[from];
        edge[pos].flow=flow;
        edge[pos].dis=dis;
        edge[pos].to=to;
        head[from]=pos;
        edge[++pos].next=head[to];
        edge[pos].flow=0;
        edge[pos].dis=-dis;
        edge[pos].to=from;
        head[to]=pos;
    }
    bool spfa(int s,int t)
    {
        CLR(dis,0x3f);
        CLR(flow,0x3f);
        CLR(vis,0);
        while (!q.empty()) q.pop();
        dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
        int tot=0;
        while (!q.empty())
        {
            int now=q.front(); q.pop(); vis[now]=0;
            for (int i=head[now]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
                {
                    dis[to]=edge[i].dis+dis[now];
                    flow[to]=min(edge[i].flow,flow[now]);
                    last[to]=i;
                    pre[to]=now;
                    if (!vis[to])
                    {
                        q.push(to); vis[to]=1;
                    }
                }
            }
        }
        return pre[t]!=-1;
    }
    void MCMF(int s,int t)
    {
        while (spfa(s,t))
        {
            int now=t;
            maxflow+=flow[t];
            mincost+=flow[t]*dis[t];
            while (now!=s)
            {
                edge[last[now]].flow-=flow[t];//dis . flow
                edge[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
    }
    struct node
    {
        int u,v,cost;
    }node[N];
    int s,t,k;
    
    int main()
    {
        RIII(n,m,k);
        rep(i,1,m)
        {
            int x;RII(node[i].u,node[i].v);RII(x,node[i].cost);
            add(node[i].u,node[i].v,x,0);
        }
        MCMF(1,n);
        cout<<maxflow;
    
        add(n,n+1,k,0);
    
        rep(i,1,m)
        {
            add(node[i].u,node[i].v,k,node[i].cost);
        }
    
        MCMF(1,n+1);
        printf(" %d",mincost);
    
        return 0;
    }

因为跑完一遍为残量网络 
    只要在这个基础上进行操作即可

首先我们记录下来跑完最大流后的残量网络。

考虑对于残量网络中的每条边 (x, y)(x,y)，在图上连一条流量无限，费用为 ww 的边。

然后从 SS 连一条边到 11，容量为 kk，以保证扩容流量正好是 kk。

只要再求一遍 SS 到 nn 的最小费用最大流就好了。

转载于:https://www.cnblogs.com/bxd123/p/10943964.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/d5fff7fb356d44268b6c17be2f9bda92.png