【BZOJ 1834】 [ZJOI2010]network 网络扩容
1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 1891 Solved: 937
[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
Sample Output
13 19
30%的数据中,N<=100
100%的数据中,N<=1000,M<=5000,K<=10
HINT
Source
Day1
最大流+费用流
第一问是最大流模板;
第二问:我们在第一问的残量网络中建立费用流模型,从s到1连流量为k,费用为0的边,并对原图中的每一条边再连上费用为
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdio>
#define M 1005
#define inf 0x3f3f3f3f
using namespace std;
int tot=1,k,n,m,cur[M],h[M],v[M],d[M],inq[M],p[M],a[M];
struct READ
{
int u,v,c,w;
}r[M*5];
struct edge
{
int from,to,cap,flow,cost,ne;
}E[200005];
void Addedge(int from,int to,int cap,int cost)
{
E[++tot]=(edge){from,to,cap,0,cost,h[from]};
h[from]=tot;
E[++tot]=(edge){to,from,0,0,-cost,h[to]};
h[to]=tot;
}
int bfs()
{
for (int i=1;i<=n;i++)
v[i]=0;
queue<int> q;
q.push(1);
v[1]=1;
d[1]=0;
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=h[x];i;i=E[i].ne)
{
edge e=E[i];
if (e.cap>e.flow&&!v[e.to])
{
v[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return v[n];
}
int dfs(int x,int a)
{
if (x==n||!a) return a;
int flow=0;
for (int &i=cur[x];i;i=E[i].ne)
{
edge &e=E[i];
if (d[e.to]!=d[x]+1) continue;
int f=dfs(e.to,min(a,e.cap-e.flow));
if (f)
{
a-=f;
e.flow+=f;
E[i^1].flow-=f;
flow+=f;
if (!a) break;
}
}
return flow;
}
int dinic()
{
int flow=0;
while (bfs())
{
for (int i=1;i<=n;i++)
cur[i]=h[i];
flow+=dfs(1,inf);
}
return flow;
}
int spfa(int &flow,int &cost)
{
for (int i=0;i<=n;i++)
d[i]=inf,inq[i]=0;
queue<int> q;
q.push(0);
inq[0]=1,d[0]=0,a[0]=inf,p[0]=0;
while (!q.empty())
{
int x=q.front();
q.pop();
inq[x]=0;
for (int i=h[x];i;i=E[i].ne)
{
edge e=E[i];
if (d[e.to]>d[x]+e.cost&&e.cap>e.flow)
{
d[e.to]=d[x]+e.cost;
p[e.to]=i;
a[e.to]=min(a[x],e.cap-e.flow);
if (!inq[e.to])
q.push(e.to),inq[e.to]=1;
}
}
}
if (d[n]==inf) return 0;
flow+=a[n];
cost+=a[n]*d[n];
int x=n;
while (x)
{
int y=p[x];
E[y].flow+=a[n];
E[y^1].flow-=a[n];
x=E[y].from;
}
return 1;
}
int mincost()
{
int flow=0,cost=0;
while (spfa(flow,cost));
return cost;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&r[i].u,&r[i].v,&r[i].c,&r[i].w);
Addedge(r[i].u,r[i].v,r[i].c,0);
}
printf("%d",dinic());
Addedge(0,1,k,0);
for (int i=1;i<=m;i++)
Addedge(r[i].u,r[i].v,inf,r[i].w);
printf(" %d\n",mincost());
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。