1. 首页
  2. 文章中心
  3. 算法

玛丽卡 （codevs p1021;洛谷p1186）玛丽卡

71 阅读 0 评论
我是靠谱客的博主 自然大叔，最近开发中收集的这篇文章主要介绍玛丽卡 （codevs p1021;洛谷p1186）玛丽卡，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

玛丽卡

堆优化Dijkstra
spfa(始终一个点TLE 希望给予优化)

题目描述

麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。
因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。
在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。
麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。
玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。
编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。

输入输出格式
输入格式：
第一行有两个用空格隔开的数N和M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用数字1至N标识，麦克在城市1中，玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A，B和V。其中1≤A，B≤N，1≤V≤1000。这些数字表示在A和城市B中间有一条双行道，并且在V分钟内是就能通过。

输出格式：

输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。

输入输出样例

输入样例#1：
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
输出样例#1：
27

个人分析

该题目本质是让求给定一个图删掉某条边后的最短路中用时最长的个。
即Ans=max{删掉第i条边最短路长} 其中（for i:=1 to m 循环）
首先未优化的方案是枚举每一条边，当该条边删掉后求最短路。
这样必然会超时，其中做了大量的不需要的计算。

∵其中当删掉的不是最短路中的一条边时，最短路显然不变，此时的运算无意义，浪费时间
∴ 先进行一遍最短路，然后枚举最短路上的边，删去后求最短路。注意必须删掉后初始化从新一遍Dijkstra，否则就有可能出错，不能认为只需从断开的节点进行最短路。

代码附带解释

代码如下

program p1021;
type link=^rec;
     rec=record
      e,v:longint;
      s:link;
     end;
     heaptype=record
      dist,point:longint;
     end;
var vertex:array[1..1000] of link;
    heap:array[1..1000] of heaptype;
    reflect:array[1..1000] of integer;
    pre:array[1..1000] of integer;
    n,m,i,s,e,v,j,maxn:longint;
    temp:heaptype;
    p:link;
procedure insert(s,e,v:longint);
begin
 new(p);
 p^.e:=e;
 p^.v:=v;
 p^.s:=vertex[s];
 vertex[s]:=p;
end;

procedure up(head,j:longint);  {堆的向上调整}
var i:longint;
begin
 while (j>>1)>=head do
  begin
   i:=j>>1;   {寻找j的父节点}
   if heap[i].dist>heap[j].dist  {依旧小的在上}
    then
     begin
      temp:=heap[i];
      heap[i]:=heap[j];
      heap[j]:=temp;
      reflect[heap[i].point]:=i;
      reflect[heap[j].point]:=j;
      j:=i;
     end
   else
    break;
 end;
end;

procedure down(i,rear:longint);   {堆的向下调整}
var j:longint;
begin
 while (i<<1)<=rear do
  begin
   j:=i<<1;  {寻找子节点}
   if (j<rear) and (heap[j].dist>heap[j+1].dist) then inc(j);  {看左右节点哪个更小}
   if heap[i].dist>heap[j].dist  {小的在上，小根堆嘛。}
    then
     begin
      temp:=heap[i];
      heap[i]:=heap[j];
      heap[j]:=temp;
      reflect[heap[i].point]:=i;
      reflect[heap[j].point]:=j;
      i:=j;
     end
    else
     break;
  end;
end;
function max(a,b:longint):longint;
begin
 if a>b then exit(a);
 exit(b);
end;

procedure dijkstra(k:longint);                  {参数k   0:表示第一次运行，此时记录路径；  1：表示删边后进行最短路}
var i,total:longint;
    visited:array[1..1000] of boolean;
begin
 for i:=1 to n do   {初始化}
  begin
   heap[i].point:=i;
   heap[i].dist:=maxlongint;    {映射关系}
   reflect[i]:=i;               {映射关系}
   visited[i]:=false;
  end;
 heap[reflect[1]].dist:=0;
 total:=n;
 up(1,reflect[1]);
 while (total>0) and (not visited[n]) do  {dijkstra}
  begin
   p:=vertex[heap[1].point];  {取出堆顶元素}
   while p<>nil do  {循环heap[1].point所连的每一条边进行更新}
    begin
     if (not ((k=1) and (heap[1].point=pre[j]) and (p^.e=j))) and (heap[reflect[p^.e]].dist>heap[1].dist+p^.v)  {k=1 and heap[1].point=pre[j]  and p^.e=j   表示这条边是已经被删去的边，并且这是删边时进行的Dijkstra}
      then
       begin
        heap[reflect[p^.e]].dist:=heap[1].dist+p^.v;
        if k=0 then pre[p^.e]:=heap[1].point;  {k=0时记录下路径，路径显然就是该点是由谁更新来的，就是走的边}
        up(1,reflect[p^.e]);{更新数据后会使得该数据变小，为保证堆的性质，此时要向上调整}
       end;
     p:=p^.s;
    end;
   visited[heap[1].point]:=true;  {堆首元素已经更新完所有与之相连的点，已经使用完毕，出堆}
   temp:=heap[1];
   heap[1]:=heap[total];
   heap[total]:=temp;
   reflect[heap[1].point]:=1;
   reflect[heap[total].point]:=total;
   dec(total);
   down(1,total); {交换后会使得堆首元素变大，所以需要向下调整}
  end;
end;

begin
 assign(input,'D:/input/codevs/p1021.txt');
 reset(input);
 assign(output,'D:/output/codevs/p1021.txt');
 rewrite(output);
 readln(n,m);
 for i:=1 to m do
  begin
   readln(s,e,v);
   insert(s,e,v);  {双行道，所以正反都插入到邻接表中}
   insert(e,s,v);
  end;
 dijkstra(0);{寻找最短路上的边}
 j:=n;
 maxn:=0;
 while j<>1 do   {j表示删掉边的终点，显然pre[j]就是这条边的起点，j=1 时已经删到头，不能再往下删，往下就没的删了，1是源点}
  begin
   dijkstra(1);
   maxn:=max(maxn,heap[reflect[n]].dist); {取较大值}
   j:=pre[j];  {删掉删一条边}
  end;
 write(maxn);
 close(input);
 close(output);
end.

评测结果

运行结果
测试点#marica1.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms 测试点#marica10.in 结果:AC
内存使用量: 624kB 时间使用量: 84ms 测试点#marica2.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica3.in 结果:AC 内存使用量: 128kB 时间使用量: 1ms 测试点#marica4.in 结果:AC
内存使用量: 256kB 时间使用量: 0ms 测试点#marica5.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#marica6.in 结果:AC 内存使用量: 496kB 时间使用量: 1ms 测试点#marica7.in 结果:AC
内存使用量: 496kB 时间使用量: 1ms 测试点#marica8.in 结果:AC 内存使用量: 496kB 时间使用量: 12ms
测试点#marica9.in 结果:AC 内存使用量: 15984kB 时间使用量: 397ms

附带超时一个点的SPFA

program p1021;
type point=^rec;
     rec=record
      e,v:longint;
      s:point;
     end;
var n,m,i,j,k,s,e,v,sum:longint;
    queue:array[1..10000] of longint;
    pre:array[1..1000] of longint;
    dist:array[1..1000] of longint;
    vertex:array[1..1000] of point;
    head,rear:longint;
    previous,maxn:longint;
    p,q:point;

function max(a,b:longint):longint;
begin
 if a>b then exit(a);
 exit(b);
end;

procedure insert(s,e,v:longint);
begin
 new(p);
 p^.e:=e;
 p^.v:=v;
 p^.s:=vertex[s];
 vertex[s]:=p;
end;

begin
 readln(n,m);
 for i:=1 to n do
  begin
   dist[i]:=maxlongint;
   pre[i]:=-1;
  end;
 for i:=1 to m do
  begin
   readln(s,e,v);
   insert(s,e,v);
   insert(e,s,v);
  end;
 head:=1;
 rear:=1;
 dist[1]:=0;
 queue[head]:=1;
 while head<=rear do
  begin
   p:=vertex[queue[head]];
   while p<>nil do
    begin
     if dist[p^.e]>dist[queue[head]]+p^.v
      then
       begin
        dist[p^.e]:=dist[queue[head]]+p^.v;
        inc(rear);
        queue[rear]:=p^.e;
        pre[p^.e]:=queue[head];
       end;
     p:=p^.s;
    end;
   inc(head);
  end;
 j:=n;
 while (j<>1) do
  begin
   for i:=1 to n do
    dist[i]:=maxlongint;
   q:=vertex[pre[j]];
   while q^.e<>j do
    begin
     q:=q^.s;
    end;
   previous:=q^.v;
   q^.v:=maxint;
   head:=1;
   rear:=1;
   dist[1]:=0;
   queue[head]:=1;
   while head<=rear do
    begin
     p:=vertex[queue[head]];
     while p<>nil do
      begin
       if dist[p^.e]>dist[queue[head]]+p^.v
        then
         begin
          dist[p^.e]:=dist[queue[head]]+p^.v;
          inc(rear);
          queue[rear]:=p^.e;
         end;
        p:=p^.s;
       end;
     inc(head);
    end;
   maxn:=max(maxn,dist[n]);
   q^.v:=previous;
   j:=pre[j]; 
  end;
 write(maxn);
end.

评测结果

运行结果
测试点#marica1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica10.in 结果:AC 内存使用量: 880kB 时间使用量: 171ms
测试点#marica2.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica3.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica4.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica5.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#marica6.in 结果:AC 内存使用量: 496kB 时间使用量: 4ms
测试点#marica7.in 结果:AC 内存使用量: 496kB 时间使用量: 7ms
测试点#marica8.in 结果:AC 内存使用量: 492kB 时间使用量: 10ms
测试点#marica9.in 结果:TLE 内存使用量: 16108kB 时间使用量: 2000ms

希望大神指出如何优化。O(∩_∩)O谢谢

#

最近变懒了。。。

说好的25号放假哪里去了= =

最后

以上就是自然大叔为你收集整理的玛丽卡 （codevs p1021;洛谷p1186）玛丽卡的全部内容，希望文章能够帮你解决玛丽卡 （codevs p1021;洛谷p1186）玛丽卡所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(47)

相关文章

【CUGBACM15级BC第30场 A】hdu 5174 Ferries WheelFerries Wheel
【CUGBACM15级BC第30场 A】hdu 5174 Ferries WheelFerries Wheel
hdu5360||多校联合第6场1008 贪心
hdu5360||多校联合第6场1008 贪心
HDU - 7073 Integers Have Friends 2.0 随机化 + 质因子题意：思路：
HDU - 7073 Integers Have Friends 2.0 随机化 + 质因子题意：思路：
bootstrab自带的轮播效果实现一个渐入和渐出效果过渡时有间隙,下一张紧跟的效果
bootstrab自带的轮播效果实现一个渐入和渐出效果过渡时有间隙,下一张紧跟的效果
玛丽卡 （codevs p1021;洛谷p1186）玛丽卡
玛丽卡 （codevs p1021;洛谷p1186）玛丽卡
洛谷1186 玛丽卡玛丽卡
洛谷1186 玛丽卡玛丽卡
玛丽卡
玛丽卡
[Wikioi 1021]玛丽卡(疑难题)
[Wikioi 1021]玛丽卡(疑难题)

评论列表共有 0 条评论

立即
投稿
返回
顶部