Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/24
07:53
图论 网络流

BZOJ 1221 [HNOI2001] 软件开发 网络流-费用流

Description

某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB,而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司经理希望费用最低。你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒,使公司在这项n天的软件开发中,提供毛巾服务的总费用最低。

Input

第1行为n,a,b,f,fA,fB. 第2行为n1,n2,……,nn. (注:1≤f,fA,fB≤60,1≤n≤1000)

Output

最少费用

Sample Input

4 1 2 3 2 1

8 2 1 6

Sample Output

38

HINT

 

Source

 

Solution

所有的毛巾可以分为两类:第i天要用的 和 第i天用完的。

第i天用完的毛巾可以以后处理,即向i+1(1≤i+1≤n)天连一条流量为INF,花费为0的边;也可以采用A种方式清洗,即向i+a+1+n(1≤i+1+a≤n)天连一条流量为INF,花费为fa的边;同理采用B种方式清洗也是这么处理。

第i天要用的毛巾也可以直接购买,由超级源s直接连一条流量为INF,花费为f的边。

超级源向每个点i连一条流量为ni,花费为0的边,每个点i+n向t连一条流量为ni,花费为0的边,限制流量。

 

02/22
15:22
图论 网络流

BZOJ 1834 [ZJOI2010]network 网络扩容 网络流-费用流

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

Solution

对于第一问,直接跑最大流算法即可。

对于第二问,在残量网络上建边,每一条边的流量为inf,费用为w,超级源跟1建边,流量为k,费用为0, 再跑最小费用最大流就好了。

(为什么可以这样? 在残量网络上,那些不需要扩容的边花费为0,所以必定会选中,不需要花费额外的花费)

 

02/22
10:52
图论 网络流

BZOJ 1877 [SDOI2009]晨跑 网络流-费用流

Description

Elaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。 现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校,保证寝室编号为1,学校编号为N。 Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路 口。Elaxia耐力不太好,他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天 数尽量长。 除了练空手道,Elaxia其他时间都花在了学习和找MM上面,所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

Input

第一行:两个数N,M。表示十字路口数和街道数。 接下来M行,每行3个数a,b,c,表示路口a和路口b之间有条长度为c的街道(单向)。

Output

两个数,第一个数为最长周期的天数,第二个数为满足最长天数的条件下最短的路程长 度。

Sample Input

7 10

1 2 1

1 3 1

2 4 1

3 4 1

4 5 1

4 6 1

2 5 5

3 6 6

5 7 1

6 7 1

Sample Output

2 11

HINT

对于30%的数据,N ≤ 20,M ≤ 120。 对于100%的数据,N ≤ 200,M ≤ 20000。

Source

Day1

Solution

拆点网络流……

 

02/22
10:32
图论 网络流

codevs 1227 方格取数2 网络流-费用流

题目描述 Description

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入描述 Input Description

第一行两个数n,k(1<=n<=50, 0<=k<=10)

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出描述 Output Description

一个数,为最大和

样例输入 Sample Input

3 1

1 2 3

0 2 1

1 4 2

样例输出 Sample Output

11

数据范围及提示 Data Size & Hint

1<=n<=50, 0<=k<=10

Solution

拆点跑费用流……