【提交地址】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