【codevs2011】最小距离之和 [LNOI2013](Floyd)

题目网址：http://codevs.cn/problem/2011/

题目大意：有一个图，每次删一条边（可以重复删），求每次删边之后所有点对的最短距离之和。

　　看了一眼题目，顿时发现了O(n^4)的暴力解法：每次删边之后跑一次Floyd，然后又看了一眼数据范围，发现n,m<=200……华丽丽的TLE……

　　删边……好像不可做……但是如果是加边就好办了。看看能不能把删边转化成加边，于是……正解思路闪现了。

　　其实这道题的思路就是把要删掉的边全部先删掉，跑一次Floyd，然后倒着加边，用加上的边更新最短路（设加上的边起点为x，终点为y，看i->x->y->j是否比直接i->j花费更小），就能在O(n^3)的时间内求出答案。

　　代码：

var a:array[..,..]of longint;

  x,y,z,ans:array[..]of longint;

  n,m,i,j,k:longint;

  b:boolean;

begin

  read(n);

  for i:= to n do

    for j:= to n do

      read(a[i,j]);//读入图

  read(m);

  for i:= to m do begin

    read(x[i],y[i]); z[i]:=a[x[i],y[i]];

    a[x[i],y[i]]:=<<;//删边

  end;

  for k:= to n do

    for i:= to n do

      for j:= to n do

        if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];//跑Floyd

  for i:=m downto  do begin

    ans[i]:=; b:=false;

    for j:= to n do begin

      for k:= to n do begin

        if a[j,k]>=<< then begin

          ans[i]:=-; b:=true; break;

        end;

        ans[i]:=ans[i]+a[j,k];

      end;

      if b then break;

    end;//算距离之和

    for j:= to n do

      for k:= to n do

        if a[j,k]>a[j,x[i]]+z[i]+a[y[i],k] then a[j,k]:=a[j,x[i]]+z[i]+a[y[i],k];//加边，更新答案

  end;

  for i:= to m do

    if ans[i]=- then writeln('INF')

    else writeln(ans[i]);//输出答案

end.

注：更新答案时不能用删掉的边直接覆盖掉原边，因为覆盖掉的花费可能更短。

巴特西

【codevs2011】最小距离之和 [LNOI2013](Floyd)

最新文章

热门文章