ZOJ Problem Set – 3265 – Strange Game

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3265

这道题相当不错,把图论问题伪装成数论了。

首先要看出来,其实这只是二分图的匹配问题。左边是ticket,右边是prize,那个公式只是用来连线的。那么自然而然想到的解法就是 最大流最小割 的 增广路算法 了。
其次,虽然题目的时间/空间复杂度并不如看上去的那么高,但显然直接把整个图构造出来也是不现实的。需要一边计算增广路,一边构造需要的那部分图。于是表现图的数据结构也和一般的稍有不同。
最后当然就是代码实现了。

前面都简单 & 顺利。然后我就在 增广路算法 那儿悲剧了。虽然知道一般用的是广度搜索(Edmonds-Karp 算法),不过为了偷懒还是上递归用深度搜索。然后无数时间没写过图的搜索算法的恶果显现。
第一次尝试,直接用了树的,然后循环了,递归堆栈跑穿直接 Segmentation Fault。修完这个,再上,然后因为没做剪枝(说白了,就是顶点着色没实现全)于是又 Time Limit Exceeded。最后加上完整的顶点着色的代码后终于 Accepted 的时候已经两个小时过去了。。。sigh

Advertisements
This entry was posted in ACM, Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s