World Final 2006 Problem J —— Routing

【提交地址】http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16007

【题目大意】

给定一个有向图G(V,E),|V|<=100,然后边数可以接近完全图。

求一个包含点数最少的强连通分量,并要求这个强连通分量包含点1和点2。

【算法分析】

一开始我和叉姐一致认为,答案应该是这样的(其中有【可怜图】标记的边代表一条包含若干点的路径):


但是实际上,围观这样一个图,它也可能是答案:

也就是说答案应当由数个环拼接而成的,但是这些环不一定只交于一个点,而有可能交在一条链上。

下面来感性地认识一下。图中的3个环用红圈标起来了。

被【可怜图】所代表的路径其实都是酱油的。关键在于环和环的交接处,也就是图中的每一列上面的。(一个点也可以看作链)

很容易发现,如果要往后并入环,那么只需要交界处的信息的就可以了。

比如说已经处理了图中的第一个环以后,如果要并入第二个环,我们需要的信息就只有8 -> 3 -> 4这条链。实际上3都不需要了,只要知道这是一条从8出发,到达4的链。然后对于另外一条链,如果要并入这个环,只需要接在8和4上就够了。

所以本质上来说,带【可怜图】的边,以及每一列的链上中间的过程都不重要,所以这些部分可以直接用最短路径代替。

处理时可以建一个数组ins[i][j],表示从i到j的路径上至少需要多少个点(这个很容易用Floyd实现),然后直接拼接就可以了。

于是很自然地想到定义状态d[i,j]表示最后以i->j的最短链作为和下一个环的公共部分,并且i->j这条最短链已经并入1点所在的环时最少需要多少个点。然后就是各条链之间转移了。由于每次转移,包含的点必然不减,也就相当于最短路中没有负权边,所以可以利用朴素的dijkstra算法求解。

最终时间复杂度O(n^4)  (一共有n^2条最短链,它们之间可能有接近完全图的边)

跑了2730MS……

求更好的算法。

【CODE】http://ideone.com/9uxRj

留下评论

您的电子邮箱地址不会被公开。