1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 2701 Solved: 1368
[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
【题解】
网络流和费用流的结合。
第一问很简单，直接跑一遍dinic即可。
第二问是费用流，将原图上的每条边上建立一条附属边，流量为k，费用为扩容费用，然后跑费用流即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1000000000
#define MAXN 5010
struct node{int x,y,next,v,c,rel;}e[MAXN*],edge[MAXN*];
int n,m,k,len,ans,Link[MAXN],level[MAXN],vis[MAXN],dis[MAXN],lastnode[MAXN],lastedge[MAXN],q[MAXN*];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void insert(int x,int y,int v,int c)
{
e[++len].next=Link[x];Link[x]=len;e[len].x=x;e[len].y=y;e[len].v=v;e[len].c=c;e[len].rel=len+;
e[++len].next=Link[y];Link[y]=len;e[len].x=y;e[len].y=x;e[len].v=;e[len].c=-c;e[len].rel=len-;
}
bool bfs()
{
memset(level,-,sizeof(level));
int head=,tail=; q[]=; level[]=;
while(++head<=tail)
for(int i=Link[q[head]];i;i=e[i].next)
if(level[e[i].y]<&&e[i].v)
{
q[++tail]=e[i].y;
level[q[tail]]=level[q[head]]+;
}
return level[n]>=;
}
int dinic(int x,int flow)
{
if(x==n) return flow;
int maxflow=,d=;
for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
if(level[e[i].y]==level[x]+&&e[i].v)
if(d=dinic(e[i].y,min(e[i].v,flow-maxflow)))
{
maxflow+=d;
e[i].v-=d;
e[e[i].rel].v+=d;
}
if(!maxflow) level[x]=-;
return maxflow;
}
void solve1()
{
int d=;
ans=;
while(bfs())
while(d=dinic(,INF))
ans+=d;
printf("%d ",ans);
}
bool spfa()
{
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
int head=,tail=,oo=dis[];
q[]=; vis[]=; dis[]=;
while(++head<=tail)
{
int x=q[head];
for(int i=Link[x];i;i=e[i].next)
if(dis[x]+e[i].c<dis[e[i].y]&&e[i].v)
{
dis[e[i].y]=dis[x]+e[i].c;
if(!vis[e[i].y])
{
q[++tail]=e[i].y;
vis[e[i].y]=;
}
lastnode[e[i].y]=x; lastedge[e[i].y]=i;
}
vis[x]=;
}
return dis[n]<oo;
}
void cost()
{
int d=k;
for(int i=n;i!=;i=lastnode[i])
if(e[lastedge[i]].v<d)
d=e[lastedge[i]].v;
for(int i=n;i!=;i=lastnode[i])
{
int j=lastedge[i];
e[j].v-=d;
e[e[j].rel].v+=d;
ans+=d*e[j].c;
}
k-=d;
}
void solve2()
{
ans=;
while(k)//控制1点的流量，相当于一个超级源的作用
{
spfa();
cost();
}
printf("%d\n",ans);
}
int main()
{
freopen("cin.in","r",stdin);
freopen("cout.out","w",stdout);
n=read(); m=read(); k=read();
for(int i=;i<=m;i++)
{
int x=read(),y=read(),v=read(),c=read();
insert(x,y,v,);
edge[i].x=x; edge[i].y=y; edge[i].c=c;
}
solve1();
for(int i=;i<=m;i++) insert(edge[i].x,edge[i].y,k,edge[i].c);
solve2();
return ;
}