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

拆点跑费用流……

 

02/7
13:43
图论 网络流

网络流二十四题-搭配飞行员 网络流-最大流

问题描述

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。


如图,假设有10个驾驶员,如图中的V1,V2,…,V10就代表达10个驾驶员,其中V1,V2,V3,V4,V5是正驾驶员,V6,V7,V8,V9,V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行,就在代表他们两个之间连一条线,两个人不能同机飞行,就不连。例如V1和V7可以同机飞行,而V1和V8就不行。请搭配飞行员,使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.

输入格式

输入文件有若干行 第一行,两个整数n与n1,表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员. 下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。 注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号.

输出格式

输出文件有一行 第一行,1个整数,表示最大起飞的飞机数。

输入输出样例

输入文件名: flyer.in
10 5
1 7
2 6
2 10
3 7
4 8
5 9

输出文件名:flyer.out
4

Solution

首先这是一张二分图,求最大匹配数。然而我并不会匈牙利算法

把所有能配对的正飞行员和副飞行员连边,跑Dinic就可以啦。

还有询问匹配方案的版本,并没有找到 而且我也不会

给一个提交地址咯 http://cogs.pro/cogs/problem/problem.php?pid=14

 

02/7
13:21
图论 网络流

jubeeeeeat 网络流-最大流

描述

众所周知,LZF很喜欢打一个叫Jubeat的游戏。这是个音乐游戏,游戏界面是4×4的方阵,会根据音乐节奏要求玩家按下一些指定方块(以下称combo)。LZF觉得这太简单了,于是自己仿了个游戏叫Jubeeeeeat,唯一不同之处就是界面大小,Jubeeeeeat的界面为n×n的方阵。 在某一刻,界面同时出现了若干个combo。LZF终于觉得有些困难了,但毕竟LZF不是普通人,他有很多只手。LZF的手分为m只“肉质手”和q只“意念手”。顾名思义,“肉质手”是实际存在的手,每只肉质手都有5根手指,每根手指能按一个combo,但每只手的速度都不同,受限于此,LZF的每只肉质手的控制范围是一个固定大小的正方形。“意念手”即虚无之手,每只手只有1根手指,但控制范围为全局。 现在LZF想知道,他最多能按下多少个combo。

输入

输入文件名为 jubeeeeeat.in。 第1行输入三个正整数n,m,q。 接下来是一个n×n的01矩阵,描述combo的位置,1为combo。 最后m行每行三个正整数xi,yi,ai,分别表示第i只肉质手掌控区域左上方块的行、列和边长。(行、列从1数起)

输出

输出文件名为 jubeeeeeat.out。 输出一个正整数,表示最多能按下的combo数。

样例输入

3 1 3
1 0 1
1 1 1
1 0 1
1 1 2

样例输出

6

提示

【数据说明】 对于20%的数据,n=5,m=2,q=2; 对于50%的数据,1≤n≤20,1≤m, q≤50; 对于100%的数据,1≤n≤40,1≤m, q≤300,1≤xi, yi≤n,1≤xi+ai-1, yi+ai-1≤n。

Solution

一个非常裸的最大流。将肉质手向控制区域内的combo连边,流量为1,意志手向所有的combo连边,流量为1.源点向肉质手连流量为5的边,向意志手连流量为1的边,所有的combo与汇点连流量为1的边。

 

01/24
20:37
图论 网络流

POJ 3281 Dining 网络流-最大流

Description

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.

Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.

Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

Input

Line 1: Three space-separated integers: N, F, and D Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

Output

Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes Sample Input

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

Sample Output

3

Hint

One way to satisfy three cows is: Cow 1: no meal Cow 2: Food #2, Drink #2 Cow 3: Food #1, Drink #1 Cow 4: Food #3, Drink #3 The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

Source

USACO 2007 Open Gold

Soluiton

网络流的裸题,敲个Dinic存个板子。 顺便说一下Dinic。 Dinic多路增广,还用到了阻塞流?嗯对……
Dinic的优化:当前弧优化,以及分层优化(针对有环的情况)

关于这道题,给定n头牛,f种食物,d种饮料,每一头牛有喜欢其中的几种饮料和食物,但是每种食物和饮料只有一个。问能最大满足多少头牛同时吃到喜欢的食物,喝到喜欢的饮料。
很容易想到建两个源汇点s,t,s向每种食物/饮料连边,每种食物/饮料向对应的牛连边,牛再向对应的饮料/食物连边,然后每种饮料/食物向t连边,流量都是1. 可是这样的话,一头牛有可能吃到多种喜欢的食物,喝到多种喜欢的饮料,显然不能得到最优解。怎么处理呢?把每头牛拆成两个点,两个点之间连一条流量为1的边,这样就处理好了。