亟隐

朝不闻道,夕亦死可矣

07/23
11:38
图论 算法区 网络流

HDU 4067 Random Maze

地址:戳这里

Problem Description
In the game “A Chinese Ghost Story”, there are many random mazes which have some characteristic:
1.There is only one entrance and one exit.
2.All the road in the maze are unidirectional.
3.For the entrance, its out-degree = its in-degree + 1.
4.For the exit, its in-degree = its out-degree + 1.
5.For other node except entrance and exit, its out-degree = its in-degree. Read More →
05/14
23:38
算法区 网络流

BZOJ 2768: [JLOI2010]冠军调查

地址:戳这里

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。

Read More →

05/14
20:46
算法区 网络流

BZOJ 2756: [SCOI2012]奇怪的游戏

地址:戳这里

Description

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。

Read More →

11/13
11:58
图论 算法区 网络流

SPOJ 2899 Volunteers 费用流

地址:戳这里

ACM ICPC World Finals 2009, sponsored by IBM and hosted by KTH, Royal Institute of Technology will be held in Stockholm, Sweden. This contest will last for N(1<= N <= 1000) days. We need at least Aivolunteers in the i-th day. Now there are M(1<= M <=10000) kind of volunteers. The i-th type of volunteers will work from Si-th day to Ti-th day, we will pay them $Ci. Now your task is to minimize the money KTH pay for all the volunteers. Read More →

08/29
17:59
图论 算法区 网络流

HDU 3722 Card Game 最大权匹配

地址:戳这里

Problem Description
Jimmy invents an interesting card game. There are N cards, each of which contains a string Si. Jimmy wants to stick them into several circles, and each card belongs to one circle exactly. When sticking two cards, Jimmy will get a score. The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card. For example, if Jimmy sticks the card S1 containing “abcd” in front of the card S2 containing “dcab”, the score is 2. And if Jimmy sticks S2 in front of S1, the score is 0. The card can also stick to itself to form a self-circle, whose score is 0. Read More →
08/26
17:46
算法区 网络流

HDU 3690 Knight's Problem 最小割

地址:戳这里

Problem Description
You may not hear about Nubulsa, an island country on the Pacific Ocean. Nubulsa is an undeveloped country and it is threatened by the rising of sea level. Scientists predict that Nubulsa will disappear by the year of 2012. Nubulsa government wants to host the 2011 Expo in their country so that even in the future, all the people in the world will remember that there was a country named “Nubulsa”. Read More →
08/20
19:36
算法区 网络流

HDU 3667 Transportation费用流

地址:戳这里

Problem Description
There are N cities, and M directed roads connecting them. Now you want to transport K units of goods from city 1 to city N. There are many robbers on the road, so you must be very careful. The more goods you carry, the more dangerous it is. To be more specific, for each road i, there is a coefficient ai. If you want to carry x units of goods along this road, you should pay ai * x2 dollars to hire guards to protect your goods. And what’s worse, for each road i, there is an upper bound Ci, which means that you cannot transport more than Ci units of goods along this road. Please note you can only carry integral unit of goods along each road.
You should find out the minimum cost to transport all the goods safely.

Read More →

07/30
19:15
算法区 网络流

SPOJ 10230 AMR11C Robbing Gringotts 费用流

地址:戳这里

The Death Eaters are low on funds, and their leader Voldemort has asked them to get more money quickly, or face his wrath.  They decide that the best way is to rob Gringotts Wizarding Bank.

By threatening one of the goblins in charge of the bank, the ‘M’ Death Eaters have discovered that Gringotts has ‘N’ vaults, with vault number ‘i’ containing  X[i] gold items.  The weights of the gold items in the ith vault are g[i][1],g[i][2],…,g[i][X[i]]. But as soon as a vault is robbed, the magical wards go off and alarm bells ring. Thus they have enough time to rob just one vault each, and all robberies have to take place at the same time. The Death Eaters have decided that no two of them will rob the same vault as this increases the chances of them being caught. Read More →