1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MB Submit: 3330 Solved: 1739 [Submit][Status][Discuss]
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
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
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
对于第一问，我们直接跑网络流。
对于第二问，我们先建一个超级源，从这个超级源向1连一条容量为k，费用为0的边。
之后对于原图的每一条边，建一条容量无限的边，跑最小费用最大流即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define maxm 5005
#define maxn 1005
using namespace std;
struct data {
int from,to,next,w,c;
}e[maxm*];
int head[maxn],cnt;
void add(int u,int v,int w,int c){e[cnt].from=u;e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;e[cnt].c=c;head[u]=cnt++;}
int n,m,k;
int q[maxn];
bool vis[maxn];
int dis[maxn];
bool bfs() {
memset(dis,-,sizeof(dis));
int h=,t=;
q[h]=;
vis[]=;
dis[]=;
while(h!=t) {
int now=q[h];h++;vis[now]=;if(h==) h=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(e[i].w&&dis[to]<) {
dis[to]=dis[now]+;
if(!vis[to]){
vis[to]=;
q[t++]=to;if(t==)t=;
}
}
}
}
return dis[n]!=-;
}
int dfs(int now,int a) {
if(now==n||a==) return a;
int flow=,f;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(dis[to]==dis[now]+&&e[i].w>) {
f=dfs(to,min(a,e[i].w));
e[i].w-=f;
e[i^].w+=f;
flow+=f;
a-=f;
if(a==) return flow;
}
}
if(!flow) dis[now]=-;
return flow;
}
void work1() {
int ans=;
while(bfs()){ans+=dfs(,);}
printf("%d ",ans);
}
int cost=;
bool spfa() {
for(int i=;i<=n;i++) dis[i]=-;
int h=,t=;
q[h]=n;
vis[n]=;
dis[n]=;
while(h!=t) {
int now=q[h];h++;vis[now]=;if(h==) h=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(e[i^].w&&dis[to]<dis[now]+e[i].c) {
dis[to]=dis[now]+e[i].c;
if(!vis[to]){
vis[to]=;
q[t++]=to;if(t==)t=;
}
}
}
}
cost-=dis[];
return dis[]!=-;
}
int ans2;
int zkw(int now,int a) {
if(now==n||a==){ans2+=cost*a;return a;}
int flow=,f;vis[now]=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(dis[to]==dis[now]+e[i].c&&e[i].w>&&!vis[to]&&(f=zkw(to,min(a,e[i].w)))) {
e[i].w-=f;
e[i^].w+=f;
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
void build() {
int t=cnt;
for(int i=;i<t;i+=) {
add(e[i].from,e[i].to,,e[i].c);
add(e[i].to,e[i].from,,-e[i].c);
}
add(,,k,);
add(,,,);
for(int i=;i<t;i++) e[i].c=;
}
void work2() {
ans2=;cost=;
build();
memset(vis,,sizeof(vis));
while(spfa()) {
do {
memset(vis,,sizeof(vis));
}while(zkw(,));
memset(vis,,sizeof(vis));cost=;
}
printf("%d",ans2);
}
int main() {
memset(head,-,sizeof(head));
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++) {
int u,v,w,c;
scanf("%d%d%d%d",&u,&v,&w,&c);
add(u,v,w,c);add(v,u,,-c);
}
work1();
work2();
}