Loi_Vampire's Blog

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

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的边,这样就处理好了。