Armin's Blog

learn,explore,create.


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

【poj-1966】 Cable TV Network(最小割+dinic)

发表于 2019-08-11 | 分类于 题解 | 阅读次数:

描述

传送门:poj-1966

 The interconnection of the relays in a cable TV network is bi-directional. The network is connected if there is at least one interconnection path between each pair of relays present in the network. Otherwise the network is disconnected. An empty network or a network with a single relay is considered connected. The safety factor f of a network with n relays is:

  1. n, if the net remains connected regardless the number of relays removed from the net.
  2. The minimal number of relays that disconnect the network when removed.

    For example, consider the nets from figure 1, where the circles mark the relays and the solid lines correspond to interconnection cables. The network (a) is connected regardless the number of relays that are removed and, according to rule (1), f=n=3. The network (b) is disconnected when 0 relays are removed, hence f=0 by rule (2). The network (c) is disconnected when the relays 1 and 2 or 1 and 3 are removed. The safety factor is 2.
阅读全文 »

【poj-343】 ACM Computer Factory (最大流记录路径)

发表于 2019-08-11 | 分类于 题解 | 阅读次数:

描述

传送门:poj-3436

 As you know, all the computers used for ACM contests must be identical, so the participants compete on equal terms. That is why all these computers are historically produced at the same factory.

Every ACM computer consists of P parts. When all these parts are present, the computer is ready and can be shipped to one of the numerous ACM contests.

阅读全文 »

【poj-2195】 Going Home(二分图带权匹配+最小费用最大流)

发表于 2019-08-11 | 分类于 题解 | 阅读次数:

描述

传送门:poj-2195

 On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that point, and am ‘m’ indicates there is a little man on that point.

You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input

阅读全文 »

【poj-3281】 Dining(拆点建图+最大流)

发表于 2019-08-10 | 分类于 题解 | 阅读次数:

描述

传送门:poj-3281

 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).

阅读全文 »

【HDU-1532】 Drainage Ditches(dinic最大流入门题)

发表于 2019-08-10 | 分类于 题解 | 阅读次数:

描述

传送门:HDU-532

 Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

阅读全文 »

F(x)

发表于 2019-07-20 | 分类于 题解 | 阅读次数:

描述

传送门:hdu-4734

 For a decimal number $x$ with $n$ digits $ (A_n A_{n-1}A_{n-2} … A_2 A_1) $, we define its weight as $F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + … + A_2 * 2 + A_1 * 1$. Now you are given two numbers A and B, please calculate how many numbers are there between $0$ and $B$, inclusive, whose weight is no more than $F(A)$.

阅读全文 »

不要62(数位dp板子题)

发表于 2019-07-20 | 分类于 题解 | 阅读次数:

描述

传送门:hdu-2089

 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

阅读全文 »

数论笔记本

发表于 2019-04-25 | 分类于 学习笔记 | 阅读次数:

数论是个好东西。

阅读全文 »

Hie with the Pie(Floyd+状压dp)

发表于 2019-04-20 | 分类于 题解 | 阅读次数:

描述

传送门:poj-3311

 The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him.

阅读全文 »

求数列的逆序数

发表于 2019-04-15 | 分类于 笔记 | 阅读次数:

描述

 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

阅读全文 »
12…8
Armin

Armin

梦里不知身是客,一晌贪欢

80 日志
5 分类
53 标签
GitHub Weibo E-Mail Facebook Twitter
友情链接
  • Phantaci
  • Angora
  • VoidR
  • fjk
  • Chengshao
  • Nico
© 2019 Armin
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4
人 次