题目描述

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

题目分析

最大流+费用流
第一问直接最大流
第二问每条边的两个端点之间连费用
最后n向t连(k,0)的边

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k,s,t;
int head[1010],to[100000],net[100000],val[100000],flo[100000];
int tot=1;
int x[100000],y[100000],va[100000],vb[100000];
void add(int x,int y,int v,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,flo[tot]=v,val[tot]=c;
    net[++tot]=head[y];head[y]=tot,to[tot]=x,flo[tot]=0,val[tot]=-c;
}
int dis[1010],vis[1010];
int path[1010];
int bfs()
{
    queue<int>q;
    memset(dis,0,sizeof dis);
    q.push(s);
    dis[s]=1;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        for(int i=head[nmp];i;i=net[i])
            if(flo[i]>0&&!dis[to[i]])
            {
                dis[to[i]]=dis[nmp]+1;
                q.push(to[i]);
                if(to[i]==t) return 1;
            }
    }
    return 0;
}
int dinic(int x,int flow)
{
    int tmp,temp=flow;
    if(x==t) return flow;
    for(int i=head[x];i;i=net[i])
        if(flo[i]>0&&dis[to[i]]==dis[x]+1)
        {
            tmp=dinic(to[i],min(flo[i],temp));
            if(tmp==0) dis[to[i]]=0;
            temp-=tmp,flo[i]-=tmp,flo[i^1]+=tmp;
            if(!temp) break;
        }
    return flow-temp;
}
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>q;
    vis[s]=1,q.push(s),dis[s]=0;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        vis[nmp]=0;
        for(int i=head[nmp];i;i=net[i])
            if(flo[i]>0&&dis[to[i]]>dis[nmp]+val[i])
            {
                dis[to[i]]=dis[nmp]+val[i];
                path[to[i]]=i^1;
                if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
            }
    }
    return dis[t]<0x3f3f3f3f;
}
int mincost()
{
    int sum=0;
    while(spfa())
    {
        int minflow=1<<30;
        for(int i=t;i!=1;i=to[path[i]]) minflow=min(minflow,flo[path[i]^1]);
        for(int i=t;i!=1;i=to[path[i]])
        {
            flo[path[i]]+=minflow;
            flo[path[i]^1]-=minflow;
            sum+=val[path[i]^1]*minflow;
        }
    }
    return sum;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d%d",&x[i],&y[i],&va[i],&vb[i]);
    for(int i=1;i<=m;i++) add(x[i],y[i],va[i],0);
    s=1,t=n;
    int ans=0;
    while(bfs()) ans+=dinic(s,1<<30);
    printf("%d ",ans);
    t=n+1;
    for(int i=1;i<=m;i++) add(x[i],y[i],1<<30,vb[i]);
    add(n,t,k,0);
    printf("%d",mincost());
    return 0;
}