Poj1734 Sightseeing trip — Floyd求最小环

Note: 本文最初于 2011年01月29日 星期六 18:46 在 hi.baidu.com/lydrainbowcat 发表。šš

朴素算法
令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路
最小环则是min(u,v) + e(u,v)。时间复杂度是O(MN^2)。

改进算法
在floyd的同时，顺便算出最小环

g[i][j]=i,j之间的边长
answer:=maxlongint;
dist:=g;
for k:=1 to n do
begin
     for i:=1 to k-1 do
         for j:=1 to i-1 do
             answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
     for i:=1 to n do
         for j:=1 to n do
             dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;

Floyd求最小环算法的证明
根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径。

一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度就是 g[i][k] + g[k][j] + “i到j的路径中,所有结点编号都小于k”的最短路径长度，即为dist[i][j]。
而我们对每个可能的k取值进行了循环遍历，综上所述，该算法一定能找到图中最小环。

打印方案：
用一个mid数组记录i与j之间的k，最后循环递归输出。例题：Tyvj1433(求ans)，Poj1734(打印方案)
程序基本一样，以poj的为例，tyvj的输出ans，加上seekeof即可。

参考程序：

Source Code

Problem: 1734		User: lydliyudong
Memory: 1320K		Time: 94MS
Language: Pascal		Result: Accepted

• Source Code

var
 a,d,mid:array[0..200,0..200]of longint;
 path:array[0..200]of longint;
 s,p,t,i,j,ans,k,n,m,x,y,z,tot:longint;

procedure print(l,r:longint);
 var
  k:longint;
 begin
  k:=mid[l,r];
  if k=0 then exit;
  print(l,k);
  inc(tot); 
  path[tot]:=k;
  print(k,r);
 end;

begin
  readln(n,m);
  filldword(a,sizeof(a)div 4,maxlongint div 10);
  fillchar(mid,sizeof(mid),0);
  for i:=1 to m do
   begin
    read(x,y,z);
    if a[x,y]>z then
     begin
      a[x,y]:=z;
      a[y,x]:=z;
     end;
   end;
  ans:=maxlongint div 10;
  d:=a;
  for k:=1 to n do
   begin
    for i:=1 to k-1 do
     for j:=i+1 to k-1 do
      if ans>d[i,j]+a[i,k]+a[j,k] then
       begin
        ans:=d[i,j]+a[i,k]+a[j,k];
        s:=i;
        p:=j;
        t:=k;
        tot:=0;
        print(s,p);
       end;
    for i:=1 to n do
    if (i<>k) then
      for j:=1 to n do
       if (i<>j)and(j<>k)and(d[i,j]>d[i,k]+d[k,j]) then
        begin
         d[i,j]:=d[i,k]+d[k,j];
         mid[i,j]:=k;
        end;
   end;
  if ans>=maxlongint div 20 then writeln('No solution.')
  else begin
   write(s,' ');
   for i:=1 to tot do write(path[i],' ');
   writeln(p,' ',t);
  end;
end.