Problem Description There is a grid with N rows and M columns. In each cell you can choose to put a golden or silver egg in it, or just leave it empty. If you put an egg in the cell, you wi...
最小割
POJ 2987 Firing 题解【网络流】【最大权闭合子图】
需要证明一个结论。然后灵活运用最大权闭合子图。 Description You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do some firings. You’re now simply too mad ...
hdu 3061 Battle 题解【网络流】【最小割】【最大权闭合子图】
最大权闭合子图的理解。 Problem Description 由于小白同学近期习武十分刻苦,很快被晋升为天策军的统帅。而他上任的第一天,就面对了一场极其困难的战斗: 据侦查兵回报,前方共有N座城池,考虑到...
hdu 3061 Battle 题解【网络流】【最小割】【最大权闭合子图】
最大权闭合子图的理解。 Problem Description 由于小白同学近期习武十分刻苦,很快被晋升为天策军的统帅。而他上任的第一天,就面对了一场极其困难的战斗: 据侦查兵回报,前方共有N座城池,考虑到...
hdu 3657 Game 题解【网络流】【最小点权覆盖集】
最小点权覆盖集的题做起来还是挺有意思的。 Problem Description onmylove has invented a game on $ n\times m grids. There is one positive integer on each grid. Now you can take the numbers fro...
POJ 2125 Destroying The Graph 题解【最小点权覆盖集】【网络流】【最小割方案】
这个题的主要难点是最小割输出方案。 Description Alice and Bob play the following game. First, Alice draws some directed graph with $ N$ vertices and $ M$ arcs. After that Bob tries to destr...
POJ 3308 Paratroopers 题解【网络流】【最小点权覆盖集】
很适合用来练习最小点权覆盖集的一个题。 Description It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are ...
洛谷 P2774 方格取数问题 题解【网络流】【最小点权覆盖集】
学到了方格图上的一种建模方向。 题目描述 在一个有 m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取...
bzoj1001/洛谷 P4001 [BJOI2006]狼抓兔子 题解【网络流】【最小割】
弃isap从dinic之路…… 题目描述 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下...
洛谷 P2805 [NOI2009]植物大战僵尸 题解【最小割】【拓扑排序】【环】【最大权闭合子图】
无法正视pvz了。。。 题目描述 Plants vs. Zombies(PVZ)是最近十分风靡的一款小游戏。Plants(植物)和Zombies(僵尸)是游戏的主角,其中Plants防守,而Zombies进攻。该款游戏包...