网络流/费用流
这题……我一开始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
1、 在不扩容的情况下,1到N的最大流;
2、 将1到N的最大流增加K所需的最小扩容费用。
Input
接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。
Output
Sample Input
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
30%的数据中,N<=100
100%的数据中,N<=1000,M<=5000,K<=10
HINT
Source
【BZOJ】【1834】【ZJOI2010】Network 网络扩容的更多相关文章
-
BZOJ 1834: [ZJOI2010]network 网络扩容(最大流+最小费用最大流)
第一问直接跑最大流.然后将所有边再加一次,费用为扩容费用,容量为k,再从一个超级源点连一条容量为k,费用为0的边到原源点,从原汇点连一条同样的边到超级汇点,然 后跑最小费用最大流就OK了. ---- ...
-
bzoj 1834: [ZJOI2010]network 网络扩容 -- 最大流+费用流
1834: [ZJOI2010]network 网络扩容 Time Limit: 3 Sec Memory Limit: 64 MB Description 给定一张有向图,每条边都有一个容量C和一 ...
-
bzoj 1834 [ZJOI2010]network 网络扩容(MCMF)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1834 [题意] 给定一个有向图,每条边有容量C,扩容费用W,问最大流和使容量增加K的最 ...
-
BZOJ 1834 [ZJOI2010]network 网络扩容(费用流)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1834 [题目大意] 给定一张有向图,每条边都有一个容量C和一个扩容费用W. 这里扩容费 ...
-
bzoj 1834: [ZJOI2010]network 网络扩容
#include<cstdio> #include<iostream> #include<cstring> #define M 100000 #define inf ...
-
bzoj 1834: [ZJOI2010]network 网络扩容【最大流+最小费用最大流】
第一问直接跑最大流即可.建图的时候按照费用流建,费用为0. 对于第二问,在第一问dinic剩下的残量网络上建图,对原图的每条边(i,j),建(i,j,inf,cij),表示可以用c的花费增广这条路.然 ...
-
BZOJ 1834: [ZJOI2010]network 网络扩容 最小费用流_最大流_残量网络
对于第一问,跑一遍最大流即可. 对于第二问,在残量网络上的两点间建立边 <u,v>,容量为无限大,费用为扩充费用. 跑一遍最小费用流即可. Code: #include <vecto ...
-
BZOJ 1834: [ZJOI2010]network 网络扩容(网络流+费用流)
一看就知道是模板题= = ,不说什么了= = PS:回去搞期末了,暑假再来刷题了 CODE: #include<cstdio> #include<iostream> #incl ...
-
【BZOJ】1834: [ZJOI2010]network 网络扩容(最大流+费用流)
http://www.lydsy.com/JudgeOnline/problem.php?id=1834 我又思考人生了T_T,nd的数组开小了,一直wa,调了一个小时才发现啊!!!!!我一直以为我的 ...
-
【BZOJ】1834 [ZJOI2010]network 网络扩容
[算法]网络流-最大流+最小费用最大流(费用流) [题解] 第一问跑最大流. 第二问: 原始边相当于费用为0的边,再原图(跑过最大流的图)基础上添加带费用的边,容量为k(相当于inf). 第一问最大流 ...
随机推荐
-
[转载]:STM32为什么必须先配置时钟再配置GPIO
转载来源 :http://blog.csdn.net/fushiqianxun/article/details/7926442 [原创]:我来添两句,就是很多同学(包括我)之前搞低端单片机,到了stm ...
-
WORDPRESS点击标题或图片无法链接到文章页面
在设置出更改固定连接设置
-
Linux下配置IP及安装vmware tool
=======================CentOS 7以下======================= 配置IP: 1.获得mac地址 2.编辑ifcfg-eth0文件:vi /etc/sy ...
-
[BZOJ2656][codevs1207][Zjoi2012]数列(sequence)
[BZOJ2656][codevs1207][Zjoi2012]数列(sequence) 试题描述 小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式: 小白作为一个数学爱好者 ...
-
signal(SIGPIPE, SIG_IGN)
文章来源:http://blog.163.com/niuxiangshan@126/blog/static/170596595201221942952676/ 当服务器close一个连接时,若cl ...
-
StringByAppendingPathComponent和stringByAppendingString的区别
cyy:自我理解,不保证正确,但亲自试验确实可行:若用 stringByAppendingString 则需要手动在名称前加 “/”符号,而stringByAppendingPathComponen ...
-
jdbc 配置properties实现
package com.web.study; import java.io.InputStream; import java.sql.Connection; import java.sql.Drive ...
-
导入Excel后绑定GridView实例
http://blog.csdn.net/loveheronly/article/details/6715552 项目中经常用到导入导出的例子,前面做了导出的例子,现在把导入Excel的数据的例子也把 ...
-
Gradle 1.12 翻译——第十五章. 任务详述
有关其他已翻译的章节请关注Github上的项目:https://github.com/msdx/gradledoc/tree/1.12,或访问:http://gradledoc.qiniudn.com ...
-
Perl导入代码文件
从函数复用开始:eval和do执行perl文件 当我们定义了一个功能比较通用的子程序,比如获取数值的绝对值.想要到处使用这个子程序,就得不断复制.粘贴这段绝对值函数的定义文本.显然,这是不太理想的方式 ...