洛谷 P2604 [ZJOI2010]网络扩容 题解【费用流】【最大流】

点击量：45

   对残量网络进一步理解( •̀ ω •́ )y

目录

题目描述

给定一张有向图，每条边都有一个容量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

说明

30%的数据中，N<=100

 

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

题解：

   首先，第一问直接isap/dinic/ek/ff求出最大流应该没什么问题，主要是第二问。

   在第二问中，可以用到第一问的残量网络，也就是可能会有只连一条边就能把原来两条分开的链连到一起的情况。这样一来两边的费用都是0，只需要花费建新边的花费。因此在原来的残量网络上存在的边，花费都是0。

   但是蓝色边的残量网络也是有限的，因此每两个原先相连的点之间还要连接流量为无穷，花费不为0的边。那既然这么多流量为无穷的边，总要有一个控制吧，我们就连一条从0到1的边，流量为k，花费为0，作为总阀。

   这样跑0到n的最小费用最大流就是答案了。

不过这样可能有人会想，如果在残量网络上跑，跑到反悔的（增广的反边）边怎么办呢？

   这是没有影响的，因为流量总会越扩越大，原来存在的流量它就存在了，如果反悔只是说明这条边其实不用跑，也就是最大流的流量还是保证了为maxflow+k的。

   如果考场上没有把握，也可以先求出最大流，然后把上面的连接残量网络改成连接原图，把总阀流量改成maxflow+k就可以了。（这种做法参考其他dalao题解）

Code：

#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3fffffff
using std::deque;
struct edge
{
    int n,v,w;
    int nxt;
    edge(int n,int v,int w,int nxt)
    {
        this->n=n;
        this->v=v;
        this->w=w;
        this->nxt=nxt;
    }
    edge()
    {
        w=0;
        nxt=-1;
    }
}e[20100];
int head[1010],ecnt=-1;
void add(int from,int to,int v,int w)
{
    e[++ecnt]=edge(to,v,w,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,0,-w,head[to]);
    head[to]=ecnt;
}
int pre[10100],gap[10100],d[10100],cur[10100],n;
void bfs()
{
    int q[10100],l=0,r=0;
    q[++r]=n;
    d[n]=1;
    gap[1]=1;
    while(l<r)
    {
        int k=q[++l];
        cur[k]=head[k];
        for(int i=head[k];~i;i=e[i].nxt)
            if(!d[e[i].n]&&e[i].w==0)
            {
                d[e[i].n]=d[k]+1;
                gap[d[e[i].n]]++;
                q[++r]=e[i].n;
            }
    }
    return;
}
int sum=0;
void isap()
{
    bfs();
    int s=1;
    pre[1]=-1;
    while(d[n]<=n)
    {
        if(s==n)
        {
            int p=pre[n],minn=123456789;
            while(~p)
            {
                minn=minn<e[p].v?minn:e[p].v;
                p=pre[e[p^1].n];
            }
            sum+=minn;
            p=pre[n];
            while(~p)
            {
                e[p].v-=minn;
                e[p^1].v+=minn;
                p=pre[e[p^1].n];
            }
            s=1;
        }
        int flag=0;
        for(int i=cur[s];~i;i=e[i].nxt)
            if(e[i].v&&d[e[i].n]+1==d[s]&&e[i].w==0)
            {
                flag=1;
                cur[s]=e[i].nxt;
                pre[e[i].n]=i;
                s=e[i].n;
                break;
            }
        if(!flag)
        {
            int tmp=d[s];
            d[s]=n+1;
            for(int i=head[s];~i;i=e[i].nxt)
                if(e[i].v&&e[i].w==0)
                    d[s]=d[s]<d[e[i].n]+1?d[s]:d[e[i].n]+1;
            gap[d[s]]++;
            gap[tmp]--;
            if(!gap[tmp])
                return;
            cur[s]=head[s];
            if(s!=1)
                s=e[pre[s]^1].n;
        }
    }
}
bool spfa()
{
    pre[0]=-1;
    int dis[10100];
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;
    int used[10100];
    memset(used,0,sizeof(used));
    dis[0]=0;
    used[0]=true;
    q.push_back(0);
    while(!q.empty())
    {
        int k=q.front();
        used[k]=0;
        q.pop_front();
        for(int i=head[k];~i;i=e[i].nxt)
            if(e[i].v&&dis[e[i].n]>dis[k]+e[i].w)
            {
                pre[e[i].n]=i;
                dis[e[i].n]=dis[k]+e[i].w;
                if(!used[e[i].n])
                {
                    used[e[i].n]=1;
                    if(q.empty()||dis[e[i].n]<dis[q.front()])
                        q.push_front(e[i].n);
                    else
                        q.push_back(e[i].n);
                }
            }
    }
    return dis[n]!=0x3f3f3f3f;
}
int main()
{
    int m,k,u,v,w,l;
    scanf("%d%d%d",&n,&m,&k);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w,&l);
        add(u,v,w,0);
        add(u,v,inf,l);//没有免费边,不然提前连边是错的
    }
    isap();
    printf("%d ",sum);

    add(0,1,k,0);
    sum=0;
    while(spfa())
    {
        int p=pre[n],minn=123456789;
        while(~p)
        {
            minn=minn<e[p].v?minn:e[p].v;
            p=pre[e[p^1].n];
        }
        p=pre[n];
        while(~p)
        {
            sum+=minn*e[p].w;
            e[p].v-=minn;
            e[p^1].v+=minn;
            p=pre[e[p^1].n];
        }
    }
    printf("%d\n",sum);
    return 0;
}