【BZOJ】【1834】【ZJOI2010】Network 网络扩容

时间:2022-06-25 03:04:36

网络流/费用流


  这题……我一开始sb了。

  第一问简单的最大流……

  第二问是要建费用流的图的……但是是在第一问的最大流跑完以后的残量网络上建,而不是重建……

  我们令残量网络上原有的弧的费用全部为0(因为如果还能走就不需要扩容),而新加的弧容量为INF,费用为给定的w[i]。

  然后跑费用流就好了……这样建的话如果是不用扩容的边它就会自己走费用为0的弧。

RE/TLE:费用流扩展时的队列/边集数组的大小 M 开小了,队列长度从N改成M,M大小从20000改成50000后AC

 /**************************************************************
Problem: 1834
User: Tunix
Language: C++
Result: Accepted
Time:36 ms
Memory:3824 kb
****************************************************************/ //BZOJ 1834
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,k,ans;
struct edge{int from,to,v,c,w;};
struct Net{
edge E[M],G[M];
int head[N],next[M],cnt;
void ins(int x,int y,int v,int c){
E[++cnt]=(edge){x,y,v,,c};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int v,int c){
ins(x,y,v,c); ins(y,x,,-c);
}
void Ins(int x,int y,int v,int c){
E[++cnt]=(edge){x,y,v,c,};
next[cnt]=head[x]; head[x]=cnt;
}
void Add(int x,int y,int v,int c){
Ins(x,y,v,c); Ins(y,x,,-c);
}
int s,t,d[N],Q[M];
bool mklevel(){
F(i,,n) d[i]=-;
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[t]!=-;
}
int dfs(int x,int a){
if (x==t) return a;
int flow=;
for(int i=head[x];i && flow<a;i=next[i])
if (E[i].v && d[E[i].to]==d[x]+){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()) ans+=dfs(s,INF);
}
int from[M];
bool inq[N];
bool spfa(){
int l=,r=-;
F(i,,n) d[i]=INF;
d[s]=; Q[++r]=s; inq[s]=;
while(l<=r){
int x=Q[l++];
inq[x]=;
for(int i=head[x];i;i=next[i])
if (E[i].v> && d[x]+E[i].c<d[E[i].to]){
d[E[i].to]=d[x]+E[i].c;
from[E[i].to]=i;
if (!inq[E[i].to]){
Q[++r]=E[i].to;
inq[E[i].to]=;
}
}
}
return d[n]!=INF;
}
void mcf(){
int x=INF;
for(int i=from[t];i;i=from[E[i].from])
x=min(x,E[i].v);
for(int i=from[t];i;i=from[E[i].from]){
E[i].v-=x;
E[i^].v+=x;
ans+=x*E[i].c;
}
}
void build(){
int t=cnt;
for(int i=;i<=t;i+=)
Add(E[i].from,E[i].to,INF,E[i].w);
}
void init(){
n=getint(); m=getint(); k=getint();
int x,y,z,w;
cnt=;
s=; t=n;
F(i,,m){
x=getint(); y=getint(); z=getint(); w=getint();
add(x,y,z,w);
}
Dinic(); build();
printf("%d ",ans);
ans=; s=;
ins(s,,k,);
while(spfa()) mcf();
printf("%d\n",ans);
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("1834.in","r",stdin);
freopen("1834.out","w",stdout);
#endif
G1.init();
return ;
}

1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 1976  Solved: 986
[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

[Submit][Status][Discuss]

【BZOJ】【1834】【ZJOI2010】Network 网络扩容的更多相关文章

  1. BZOJ 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容&lpar;最大流&plus;最小费用最大流&rpar;

    第一问直接跑最大流.然后将所有边再加一次,费用为扩容费用,容量为k,再从一个超级源点连一条容量为k,费用为0的边到原源点,从原汇点连一条同样的边到超级汇点,然  后跑最小费用最大流就OK了. ---- ...

  2. bzoj 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容 -- 最大流&plus;费用流

    1834: [ZJOI2010]network 网络扩容 Time Limit: 3 Sec  Memory Limit: 64 MB Description 给定一张有向图,每条边都有一个容量C和一 ...

  3. bzoj 1834 &lbrack;ZJOI2010&rsqb;network 网络扩容(MCMF)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1834 [题意] 给定一个有向图,每条边有容量C,扩容费用W,问最大流和使容量增加K的最 ...

  4. BZOJ 1834 &lbrack;ZJOI2010&rsqb;network 网络扩容(费用流)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1834 [题目大意] 给定一张有向图,每条边都有一个容量C和一个扩容费用W. 这里扩容费 ...

  5. bzoj 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容

    #include<cstdio> #include<iostream> #include<cstring> #define M 100000 #define inf ...

  6. bzoj 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容【最大流&plus;最小费用最大流】

    第一问直接跑最大流即可.建图的时候按照费用流建,费用为0. 对于第二问,在第一问dinic剩下的残量网络上建图,对原图的每条边(i,j),建(i,j,inf,cij),表示可以用c的花费增广这条路.然 ...

  7. BZOJ 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容 最小费用流&lowbar;最大流&lowbar;残量网络

    对于第一问,跑一遍最大流即可. 对于第二问,在残量网络上的两点间建立边 <u,v>,容量为无限大,费用为扩充费用. 跑一遍最小费用流即可. Code: #include <vecto ...

  8. BZOJ 1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容(网络流&plus;费用流)

    一看就知道是模板题= = ,不说什么了= = PS:回去搞期末了,暑假再来刷题了 CODE: #include<cstdio> #include<iostream> #incl ...

  9. 【BZOJ】1834&colon; &lbrack;ZJOI2010&rsqb;network 网络扩容(最大流&plus;费用流)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1834 我又思考人生了T_T,nd的数组开小了,一直wa,调了一个小时才发现啊!!!!!我一直以为我的 ...

  10. 【BZOJ】1834 &lbrack;ZJOI2010&rsqb;network 网络扩容

    [算法]网络流-最大流+最小费用最大流(费用流) [题解] 第一问跑最大流. 第二问: 原始边相当于费用为0的边,再原图(跑过最大流的图)基础上添加带费用的边,容量为k(相当于inf). 第一问最大流 ...

随机推荐

  1. &lbrack;转载&rsqb;&colon;STM32为什么必须先配置时钟再配置GPIO

    转载来源 :http://blog.csdn.net/fushiqianxun/article/details/7926442 [原创]:我来添两句,就是很多同学(包括我)之前搞低端单片机,到了stm ...

  2. WORDPRESS点击标题或图片无法链接到文章页面

    在设置出更改固定连接设置

  3. Linux下配置IP及安装vmware tool

    =======================CentOS 7以下======================= 配置IP: 1.获得mac地址 2.编辑ifcfg-eth0文件:vi /etc/sy ...

  4. &lbrack;BZOJ2656&rsqb;&lbrack;codevs1207&rsqb;&lbrack;Zjoi2012&rsqb;数列&lpar;sequence&rpar;

    [BZOJ2656][codevs1207][Zjoi2012]数列(sequence) 试题描述 小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式: 小白作为一个数学爱好者 ...

  5. signal&lpar;SIGPIPE&comma; SIG&lowbar;IGN&rpar;

    文章来源:http://blog.163.com/niuxiangshan@126/blog/static/170596595201221942952676/   当服务器close一个连接时,若cl ...

  6. StringByAppendingPathComponent和stringByAppendingString的区别

    cyy:自我理解,不保证正确,但亲自试验确实可行:若用 stringByAppendingString  则需要手动在名称前加 “/”符号,而stringByAppendingPathComponen ...

  7. jdbc 配置properties实现

    package com.web.study; import java.io.InputStream; import java.sql.Connection; import java.sql.Drive ...

  8. 导入Excel后绑定GridView实例

    http://blog.csdn.net/loveheronly/article/details/6715552 项目中经常用到导入导出的例子,前面做了导出的例子,现在把导入Excel的数据的例子也把 ...

  9. Gradle 1&period;12 翻译——第十五章&period; 任务详述

    有关其他已翻译的章节请关注Github上的项目:https://github.com/msdx/gradledoc/tree/1.12,或访问:http://gradledoc.qiniudn.com ...

  10. Perl导入代码文件

    从函数复用开始:eval和do执行perl文件 当我们定义了一个功能比较通用的子程序,比如获取数值的绝对值.想要到处使用这个子程序,就得不断复制.粘贴这段绝对值函数的定义文本.显然,这是不太理想的方式 ...