2011年08月 存档

刷不动题了 = =

2011年08月21日,星期日

刷不动题了 = =,下午把网络流做的题目总结下吧。。

ZOJ 3055 WW’s game (模拟题)

2011年08月21日,星期日

ZOJ 3055 WW’s game

昨天下午新人比赛,我想找个模拟题,然后从大黄的题解上随便找了一个,比赛中途,我想敲敲试试,没想到光看题就用了20分钟,敲题用了半个多小时,最后到吃饭时候也没把样例给过了,心情十分郁闷。晚上回去,突然发现那些候选数字是以0为结尾的,于是我就换个结束的方法while( scanf(“%d”,&n) && n );然后他就华丽丽地在我的眼前AC了。

模拟对对碰,不过规则改了改,他不是交换两个相邻的格子,而是移动一行或一列,如果存在三个颜色相同的在一行或者一列,消去。说实话,难度不大。需要注意的两点:1.把k个操作保存起来再进行模拟,2. 候选格子是以0结尾的,不一样都放在一行输入上。我的代码用类把各种操作封装了。。

(更多…)

ZOJ 2332 Gems (最大流构图)

2011年08月15日,星期一

ZOJ 2332 Gems

alsomagic 想给女朋友送宝石,但是gf不希望某种颜色太多,alsomagic 也不希望留在手中的宝石某种形状的太多(这个在刚开始看题时候理解不清楚,哎),还好alsomagic 有超能力,能让A形状B颜色的转换成C形状D颜色的,问能不能产生合适的分配。

 

(更多…)

POJ 1679 The Unique MST (判断MST是否唯一)

2011年08月15日,星期一

POJ 1679 The Unique MST

题目中给出一个无向图,需要判断mst是否唯一。

本题用prim算法来做比较简单,具体来说,当一个节点被两个边更新的时候,如果他被选为下一个放入树中的点,那么连接他的边我们就不能确定了,也就是可能有多个最小生成树。上图,当a点确定的时候,b点更新为8,c点更新为12,然后b被加入树中,然后要更新c点,这时c的值12已经被两条边更新了,所以就可能产生多棵树。

(更多…)

ZOJ 2532 Internship (寻找关键割边)

2011年08月15日,星期一

ZOJ 2532 Internship

城市宽带网络,由于不够用,所以需要扩大某些线路的容量,这样就可以增大网络的流量,你的任务就是寻找到这些边使得这些边容量一扩充就能增大流量。

每个城市都是源点,所以建立超级源点S,然后求S到T的最大流,从S开始dfs把点染色为1,再从T开始dfs把点染色成2,如果我们能找到一条边u,v一边是1,一边是2的话,这条边就是关键割边。注意割边不一定是关键的,因为对它扩容之后,与他临接的可能还是满流。。
(更多…)

POJ 3635 Full Tank? (bfs+优先队列)

2011年08月13日,星期六

POJ 3635 Full Tank?

我有种DP的感觉,也有种最短路的感觉,然后我就无语了。。

每个加油的地方要分拆成(c+1)个点,然后求最短路,但是我实在是太土了,真的是把点弄成了N(C+1)个,还建图了好多次,TLE到无语。。

后来看了题解,各种不明白,因为对所给图形的理解不是很好,这个题硬是搞了一天。

以前做过几个bfs优先队列的,但是对他的理解不是很深刻,现在慢慢了解,他跟dijkstra非常神似,也是一个贪心的过程,每次弹出最小量,然后他对应的那个值就确定了,因为他之后的不可能被更改。赶紧去找几个类似题目练练手~~~
(更多…)

UVA 10246 Asterix and Obelix (最短路变形)

2011年08月12日,星期五

UVA 10246 Asterix and Obelix

乍看是带点权的最短路,实际上最短路再加上最大点权最小的时候才是最短,即min{ path(S,T) + min{w[i]|i on path from S to T}}.我表示没有思路,看的题解做的。。比如说我们要求出S,T的“最短路”,我们可以枚举最大中间节点,因为这条路必经经过一个最大中间节点,比如说我们找到点U的时候,就假设U是S到T路径上点权最大的点,可以把图上点权大于U的点去掉然后d[ S, U ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”,每给出一个询问,查询即可。

(更多…)

POJ 2125 Destroying The Graph (最大点权覆盖集)

2011年08月10日,星期三

POJ 2125  Destroying The Graph

破坏一个棵树的,就是把他的所有边都删掉,现在有两种方式就是删掉i点的所有入边,还有就是删掉i点的所有出边,所需要的费用为Wi+,Wi-,每一条边<u,v>要被销掉,要么删除u的所有出边,要么删除v的所有入边,每条边都至少与一种操作相关联,我们可以联想到二分图的最小点集覆盖,求最小的点集,让所有的边都与之关联。对于这个题来说就是典型的模型了。二分图的最小点权覆盖,AMBER的论文第30页有讲,不再赘述,注意不要把边权选错了,入度的权在右边。。。我因为这个搞了一个下午。

还有,我的最大流模板已经十分完善了,就在blog上放我的模板,以后会填上费用流,强连通等的并且不断改进:

 

(更多…)

POJ 2987 Firing (构图 最大点权闭合集)

2011年08月8日,星期一

POJ 2987 Firing

题目就不在赘述,很裸的最大点权闭合集,在《最小割模型在信息学竞赛中的应用》有证明,但是呢,我看的不是很懂,今天早上看了一早上,下午又看了一会,还不是很明白,真坑跌,我怎么就理解不了最小割呢?哎,路漫漫,网络流的各种模型我什么时候才能搞懂啊 = =

虽然我不懂,,,但是AC还是没有问题的。。。
(更多…)

搞尼玛ACM啊,操~!~

2011年08月7日,星期日

搞尼玛啊,搞搞搞,被搞OI 的虐就算了,还被学了三个月的新人虐,CNMD~