SGU 185 — Two Shortest
经典的最短路+网络流的题目.
第一行n,m,表示n个点m条边.接下来m行,每行描述一条无向边.x y z表示x,y之间一条无向边,长度为z.要求求出两条没有公共边的最短路.
首先一个SPFA,目的是保留dist数组.然后从最后一个结点开始BFS.对于BFS到某个结点x,如果结点y能够满足dist[y]+table[x, y]=dist[x],则将这条边作为y->x的有向边加入新图中,并将y加入BFS队列(如果y没有被加入过).这样,新图中的边便都是能够构成最短路的边了.接下来对于新图,每条边的容量都看作1,源是1,汇是n,做最大流.得出的最大流就是最短路条数.如果条数少于2,输出无解.如果大于等于2,那么这时我们会获得刚刚计算最大流时的flow数组.从源开始进行DFS,每次只走flow=1的结点,直到走到汇为止,把这条路径上所有flow都变成0.然后再走一次.得到的两条路径输出即可.
然后呢,我的网络流写的是Dinic.于是,我的SPFA+Dinic就华丽的MLE掉了.
谁知道怎么优化内存…开链表不管用,链表会让内存更大.
Update:经过一晚上恶心死人的优化,终于AC了这道题.因为Delphi没有integer类型(Delphi的integer=fpc的longint…而我找不到相当于fpc的integer的类型),于是优化难了很多.最后用上了word,shortint和子界类型,终于AC掉.题目限制1MB内存,我用了1009KB,好险…另外据Wind牛说,可以用最小费用流解.只要加一个源,流2的流量就行.似乎Wind牛还有一个两遍SPFA的算法,未证明正确性.
{ SGU 185; Two shortest - sqybi’s code - 单源最短路 + 最大流 - SPFA + Dinic}//for my winstyprogram sgu185_sqybi; const nn = 400; mm = nn * nn div 2; unable = nn * 10000 + 1;
var n, m, i, qe, qs, r, edgeNum, x, y, z: longint; t: array[1..nn, […]