Posts Tagged “graph”


Andrew Stankevich’s Contest #9
ZOJ2696 Chip Designing 19.15% (41/214)
ZOJ2697 Electricity 16.55% (76/459)
ZOJ2698 Numbers to Numbers 10.28% (29/282)
ZOJ2699 Police Cities 19.35% (66/341)
ZOJ2700 Quadratic Equation 30.51% (65/213)
ZOJ2701 Restore the Tree 13.99% (76/543)
ZOJ2702 Unrhymable Rhymes 28.86% (153/530)
ZOJ2703 Selling Tickets 21.79% (51/234)

灰灰灰灰灰灰长好的一套题,所有题目都推荐!特别是2696 Chip Designing2701 Restore the Tree2697 Electricity这三道构造题,一道比一道值得一想。然后是ZOJ 2698,DP虽然简单,但英语转数字可是相当考验基本功啊。2703 Selling Tickets虽然不算难,但把握时间复杂度和编程复杂度的trade off是很有趣的一件事。有些题,尤其是构造题,一定存在更有趣,更简洁,或者更高效的算法。抛砖引玉,欢迎分享或者cha。

ZOJ2696 Chip Designing

downloadsource code (ZOJ2696.cpp) [构造, 平面几何]

给你个芯片,要用水平或垂直的线路连接两排输入输出节点,要求线路不相交。

2696-2

构造,方法应该非常多,bfs应该也可以,我的方法不难想,效率也满高的,不过写起来就不那么轻松了。首先直接构造一个input到output的连线,如果这条连线和先前的连线相交了,那么总可以“绕”过这条连线,绕的时候,可以保持这条连线的距离为u。只要每次的u都小于上回的一半(理论上等于也可以,但会有更多情况需要处理),那么就不可能会和之前的连线相交。这样还可以在计算过程中使用整数运算,不需要分数。上图是sample的情况,下图是对n=4的一个case的解,图片太模糊了,若需要高清无码矢量图,请点链接下载eps格式的文件。

DL 2696-2.ps
2696-4
DL 2696-4.ps

ZOJ2697 Electricity

downloadsource code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]

给定一个有向无环图,要求每天改变一条边的方向,使得最后一些边的方向恰好与原来相反,要求中间过程始终没有环。

Comments 6 Comments »


Andrew Stankevich’s Contest #5
ZOJ2587 Unique Attack 21.20% (263/1240)
ZOJ2588 Burning Bridges 23.92% (410/1714)
ZOJ2589 Circles 18.57% (120/646)
ZOJ2590 Linear Programming Dual 30.65% (42/137)
ZOJ2591 DVD 13.78% (79/573)
ZOJ2592 Think Positive 40.56% (527/1299)
ZOJ2593 Ranking 21.93% (84/383)
ZOJ2594 Driving Straight 19.64% (168/855)

好像是最水的一套,推荐ZOJ 2589欧拉公式太妙了;再则推荐一下ZOJ 2591的DP吧,还是很值得一写的。

ZOJ2587 Unique Attack

downloadsource code (ZOJ2587.cpp) [FlowNetwork]

恐怖分子计划用最小的代价破坏网络,以阻断AB之间的通信,问其方案是否唯一。

用最小的代价破坏AB间的网络,这就是网络流的最小割问题,于是这题就是问网络流的最小割是否唯一。判断最小割割是否唯一,我的方法是这样的,先求最大流,如果在残留网络中,从A出发bfs得到的割边和从B出发得到的一样,那么割就是唯一的。

ZOJ2588 Burning Bridges

downloadsource code (ZOJ2588.cpp) [Graph]

M个桥连通者N个岛屿,现在一些桥将被烧毁,但岛屿连通性不变,问那些桥一定不会烧毁。

题目要求的正是无向图的割边),dfs可解,可参考黑书2.4.4,注意重边的处理。

ZOJ2589 Circles

downloadsource code (ZOJ2589.cpp) [geometry, math, Euler's formula]

给定平面上的N个圆,问整个平面被分成了几个部分。

如果用圆离散化来解就太大自然了。这里可以用传说中的欧拉公式(Euler’s formula),χ=V-E+F来计算,V-vertices表示顶点数,E-edges表示边数,F-faces表示围成的面数。于是面的个数可以这样计算:对于几个相连的圆,其内有F=E-V+1个面,其中1是平面图情况的欧拉欧拉示性数(Euler characteristic);对于一个独立的圆,显然F=1;最后答案还要加上外部那个无穷大的面。通过求圆与圆的交点可以很容易的得到顶点数,边数和圆与圆是否相连,从而求得答案。

ZOJ2590 Linear Programming Dual

downloadsource code (ZOJ2590.cpp) [simulation]

输入线性规划,输出其对偶线性规划。

Comments 1 Comment »