bzoj 1834: [ZJOI2010]network 网络扩容 -- 最大流+费用流

1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec Memory Limit: 64 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

HINT

先跑一遍最大流

然后在残留网络建边对于每条边重新建一条容量inf的边（注意原边不变且费用为0）

然后就直接跑费用流

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 100000007

#define ll long long

#define N 50010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int T;

int fro[N],to[N],lj[N],v[N],w[N],fa[N],cnt=,tw[N];

void add(int a,int b,int c,int d){fro[++cnt]=lj[a];to[cnt]=b;fa[cnt]=a;v[cnt]=c;tw[cnt]=d;lj[a]=cnt;}

void ins(int a,int b,int c,int d){add(a,b,c,d);add(b,a,,-d);}

int dis[N],q[N],from[N],ans,h,t;

bool vs[N];

bool bfs()

{

    memset(dis,,sizeof(dis));

    dis[]=q[]=t=;h=;

    int tp;

    while(h!=t)

    {

        tp=q[h++]; if(h==N) h=;

        for(int i=lj[tp];i;i=fro[i])

        {

            if(!dis[to[i]]&&v[i])

            {

                dis[to[i]]=dis[tp]+;

                q[t++]=to[i]; if(t==N) t=;

            }

        }

    }

    return dis[T]?:;

}

int dfs(int x,int p)

{

    if(x==T) return p;

    int tp,res=;

    for(int i=lj[x];i;i=fro[i])

    {

        if(v[i]&&dis[to[i]]==dis[x]+)

        {

            tp=dfs(to[i],min(p-res,v[i]));

            v[i]-=tp;

            v[i^]+=tp;

            res+=tp;

            if(res==p) return p;

        }

    }

    if(res==) dis[x]=;

    return res;

}

void dinic(){while(bfs()) ans+=dfs(,inf);}

bool spfa()

{

    memset(dis,0x3f,sizeof(dis));

    int x;

    h=q[]=dis[]=;t=vs[]=;

    while(h!=t)

    {

        x=q[h++]; if(h==N) h=;

        for(int i=lj[x];i;i=fro[i])

        {

            if(v[i]&&dis[to[i]]>dis[x]+w[i])

            {

                dis[to[i]]=dis[x]+w[i];

                from[to[i]]=i;

                if(!vs[to[i]])

                {

                    vs[to[i]]=;

                    q[t++]=to[i];if(t==N) t=;

                }

            }

        }

        vs[x]=;

    }

    return dis[T]<inf;

}

void qaz()

{

    int tmp=inf;

    for(int i=from[T];i;i=from[fa[i]]) tmp=min(tmp,v[i]);

    for(int i=from[T];i;i=from[fa[i]])

    {

        v[i]-=tmp;v[i^]+=tmp;

        ans+=w[i]*tmp;

    }

}

void add2(int a,int b,int c,int d){fro[++cnt]=lj[a];to[cnt]=b;fa[cnt]=a;v[cnt]=c;w[cnt]=d;lj[a]=cnt;}

void ins2(int a,int b,int c,int d){add2(a,b,c,d);add2(b,a,,-d);}

void build()

{

    int tp=cnt;

    for(int i=;i<=tp;i+=) ins2(fa[i],to[i],inf,tw[i]);

}

int n,m,k,a,b,c,d;

int main()

{

    T=n=rd();m=rd();k=rd();

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

    {

        a=rd();b=rd();c=rd();d=rd();

        ins(a,b,c,d);

    }

    dinic();

    printf("%d ",ans);

    ans=;build();

    ins(,,k,);

    while(spfa()) qaz();

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

    return ;

}

秒客网