1834. [ZJOI2010]网络扩容【费用流】

Description

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。

求：

1、在不扩容的情况下，1到N的最大流；

2、将1到N的最大流增加K所需的最小扩容费用。

Input

第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。

接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

N<=1000，M<=5000，K<=10

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

这个思路非常的妙啊……被宽嫂一语点醒emmm
首先第一问求最大流是裸的问题瞎搞搞就行了……
不过我懒得再写一个Dinic就直接用的费用流跑的最大流
第二问我们将边拆掉
一条为容量为原本容量，费用为0
另一条容量为INF，费用为扩容费用（这意味着这个边可以无限扩容）
然后跑最小费用最大流就好了
那么k如何限定呢？
我们只需要再建立一个新汇点
在原汇点和新汇点间连接一条容量为MaxFlow+k的边，费用为0即可。
趁着宽嫂不注意
STO%%%Cansult%%%OTZ

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #define MAXN (5000+10)

 #define MAXM (50000+10)

 using namespace std;

 queue<int>q;

 bool visit[MAXN];

 int pre[MAXN];

 int n,m,k,s,e,Ans,Fee;

 int num_edge;

 int head[MAXN];

 int dis[MAXN];

 bool used[MAXN];

 int INF;

 struct node

 {

     int to;

     int next;

     int Flow;//残留网络

     int Cost;

 }edge[MAXM*];

 void add(int u,int v,int l,int c)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     edge[num_edge].Flow=l;

     edge[num_edge].Cost=c;

     head[u]=num_edge;

 }

 bool Spfa(int s,int e)

 {

     memset(pre,-,sizeof(pre));

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

     q.push(s);

     dis[s]=;

     used[s]=true;

     while (!q.empty())

     {

         int x=q.front();

         q.pop();

         for (int i=head[x];i!=;i=edge[i].next)

             if (dis[x]+edge[i].Cost<dis[edge[i].to] && edge[i].Flow>)

             {

                 dis[edge[i].to]=edge[i].Cost+dis[x];

                 pre[edge[i].to]=i;

                 if (!used[edge[i].to])

                 {

                     used[edge[i].to]=true;

                     q.push(edge[i].to);

                 }

             }

         used[x]=false;

     }

     return (dis[e]!=INF);

 }

 void MCMF(int s,int e)

 {

     Ans=,Fee=;

     while (Spfa(s,e))

     {

         int d=INF;

         for (int i=e;i!=s;i=edge[((pre[i]-)^)+].to)

             d=min(d,edge[pre[i]].Flow);

         for (int i=e;i!=s;i=edge[((pre[i]-)^)+].to)

         {

             edge[pre[i]].Flow-=d;

             edge[((pre[i]-)^)+].Flow+=d;

         }

         Ans+=d;

         Fee+=d*dis[e];

     }

 }

 int main()

 {

     int u[MAXM],v[MAXM],l[MAXM],c[MAXM];

     memset(&INF,0x7f,sizeof(INF));

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

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

     {

         scanf("%d%d%d%d",&u[i],&v[i],&l[i],&c[i]);

         add(u[i],v[i],l[i],);

         add(v[i],u[i],,);

     }

     MCMF(,n);

     printf("%d ",Ans);//MaxFlow

     memset(head,,sizeof(head));

     num_edge=;

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

     {

         add(u[i],v[i],l[i],);

         add(v[i],u[i],,);

         add(u[i],v[i],INF,c[i]);

         add(v[i],u[i],,-c[i]);

     }

     add(n,n+,Ans+k,);

     add(n+,n,,);

     MCMF(,n+);

     printf("%d",Fee);

 }

秒客网