C++之路进阶——codevs1362（网络扩容）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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 ;
}