1362 网络扩容
省队选拔赛
时间限制: 2 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：
1、 在不扩容的情况下，1到N的最大流；
2、 将1到N的最大流增加K所需的最小扩容费用。
输入描述 Input Description
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
输出描述 Output Description
输出文件一行包含两个整数，分别表示问题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
数据范围及提示 Data Size & Hint
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
题解：
在最大流的参与网络上加新边跑最小费用最大流！
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define maxn 10010
#define inf 0x7fffffff
#define S 1
#define T n using namespace std; int n,m,K,cnt=,vw[maxn],ans1,ans2,U[maxn],V[maxn],head[maxn],x,dis[maxn],inq[maxn],from[maxn]; struct ss
{
int to;
int next;
int c;
int w;
int from;
}e[]; void add(int u,int v,int c,int w)
{
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].from=u;
e[cnt].c=c;
e[cnt].w=w;
head[u]=cnt;
} void insert(int u,int v,int c,int w)
{
add(u,v,c,w);
add(v,u,,-w);
} bool bfs()
{
for (int i=;i<=T;i++) dis[i]=inf;
queue<int> que;
que.push(S);
dis[S]=;
while (!que.empty())
{
int now=que.front();
que.pop();
for (int i=head[now];i;i=e[i].next)
if (e[i].c&&dis[e[i].to]>dis[now]+)
{
dis[e[i].to]=dis[now]+;
que.push(e[i].to);
if (e[i].to==T) return ;
}
}
return ;
} int dinic(int x,int INF)
{
if (x==T) return INF;
int rest=INF;
for (int i=head[x];i;i=e[i].next)
if (e[i].c&&dis[e[i].to]==dis[x]+)
{
int now=dinic(e[i].to,min(rest,e[i].c));
e[i].c-=now;
if (!now) dis[now]=;
e[i^].c+=now;
rest-=now;
}
return INF-rest;
} bool spfa()
{
for (int i=;i<=T;i++) dis[i]=inf;
queue<int> que;
que.push();
inq[]=;
dis[]=;
while (!que.empty())
{
int now=que.front();
que.pop();
inq[now]=;
for (int i=head[now];i;i=e[i].next)
if (e[i].c&&dis[e[i].to]>dis[now]+e[i].w)
{
dis[e[i].to]=dis[now]+e[i].w;
from[e[i].to]=i;
if (!inq[e[i].to])
{
inq[e[i].to]=;
que.push(e[i].to);
}
}
}
if (dis[T]==inf) return ;
else return ;
} int bcf()
{
int x=inf;
for (int i=from[T];i;i=from[e[i].from])
x=min(x,e[i].c);
for (int i=from[T];i;i=from[e[i].from])
{
ans2+=x*e[i].w;
e[i].c-=x;
e[i^].c+=x;
}
} int main()
{
scanf("%d%d%d",&n,&m,&K);
for (int i=;i<=m;i++)
{
int u,v,w,c;
scanf("%d%d%d%d",&U[i],&V[i],&c,&vw[i]);
insert(U[i],V[i],c,);
}
while (bfs())
while (x=dinic(S,inf)) ans1+=x;
insert(,,K,);
printf("%d ",ans1);
for (int i=;i<=m;i++)
insert(U[i],V[i],K,vw[i]);
while(spfa()) bcf();
printf("%d\n",ans2);
return ;
}