Posted by watashi in solution, tags: andrewzta, DP, graph, math, solution, ZOJ
 恐怖分子计划用最小的代价破坏网络,以阻断AB之间的通信,问其方案是否唯一.
 用最小的代价破坏AB间的网络,这就是网络流的最小割问题,于是这题就是问网络流的最小割是否唯一.判断最小割割是否唯一,我的方法是这样的,先求最大流,如果在残留网络中,从A出发bfs得到的割边和从B出发得到的一样,那么割就是唯一的.
 M个桥连通者N个岛屿,现在一些桥将被烧毁,但岛屿连通性不变,问那些桥一定不会烧毁.
 题目要求的正是无向图的桥(割边),dfs可解,可参考黑书2.4.4,注意重边的处理.
 给定平面上的N个圆,问整个平面被分成了几个部分.
 输入线性规划,输出其对偶线性规划.
 熟悉对偶线性规划的话应该会有帮助,不过不熟悉也完全不要紧,线性规划的格式在不同文献里都可能不一样,在这里就得按大妈的规矩.注意>还是<的变化在min/max是不一样的,而sample只有min的.对偶线性规划的对偶线性规划应该是自己,所以把sample input和sample output对换一下又是两组case.
 Johnie从他的uncle那继承了一大堆片,不知哪的规矩,看片居然一定要按年份的顺序,更悲剧的是每个片都有个region,DVD要设置成相应的region才能看,DVD只能改5次region.问最多能看多少片,要求输出方案.
 动态规划,可以用dp[i][j][k]表示看到第i年,DVD的region最后设为j,改过k次region的情况下,所能看的最多片数.注意一年可以看超过两个region的,但是dp的时候不能一个片看多次......所以转移时,需要枚举这一年DVD都设置成过哪些region,然后贪心的把这些region的片都看了.DP不难想,但不是很好写.
 问有多少不同的j,使得对任意k,sjk恒为正.
 略.
 本质上是求最短路,不过输入和输出比较奇怪.
 先从右上角开始bfs出每个点到右上角的最短距离,再从左下角出发,每次都从距离为d的点走到相邻距离为d-1的点,模拟并输出答案就可以了.
 This entry was posted on Saturday, April 3rd, 2010 at 4:26 pm and is filed under solution. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
 One Response to "Andrew Stankevich's Contest #5解题报告"
 这个姿势好优越= =,看不懂.
 Wordpress Hashcash needs javascript to work, but your browser has javascript disabled. Your comment will be deleted!