首页 » C++ » ccf-csp之地铁修建(最小堆dijkstra算法)

ccf-csp之地铁修建(最小堆dijkstra算法)

原文 http://blog.csdn.net/yulijuanxmu/article/details/77970278

2017-09-13 22:20:21阅读(165)

要看题目的思路和代码的直接跳过这一部分。。。

做此题的心路历程

  咳咳,要开始讲了哇,因为我的蜗牛速度(对图的各种算法和基础的C++语法不熟练),所以这道题算是做了两天吧。从昨天上午到今天下午。现在我要正式开讲啦~~
  接到题目,思考了一会儿,我就认为这是一个最短路径的问题(虽然后面查到网上大部分答案都是用最小生成树做的,这是后话~),然后我开始翻严蔚敏老师的《数据结构》,找到图的最短路径这一部分,啊,熟悉的两个算法名字,dijkstra算法和Floyd算法。然鹅,实在是忘了,所以花了可能两三个小时,来温习了这两个算法。之所以花了这么久,是因为我在看dijkstra算法的“正确性证明”这一部分脑子好久都没有拐过弯来(恩,我很认真的,正确性证明都要看的喔~)。让我疑惑不解,怀疑人生的是这段话“假设S为已求得最短路径的终点的集合,则可以证明:下一条最短路径(设其终点为x)或者是弧(v,x),或者是中间只经过S中的顶点而最后达到顶点x的路径。这可以用反证法来证明。假设此路径上有一个顶点不在S中,则说明存在一条终点不在S而长度比此路径短的路径。但是,这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的,故长度比此路径短的所有路径均已经产生,它们的终点必定在S中,即假设不成立”。(补充说明:v是源点)。关键是对“则说明存在一条终点不在S而长度比此路径短的路径”的理解,这个路径到底是啥,一脸懵x,后来上网查了一下。意思是:设这个不在S中的点为k,则到x的路径可以分为两段(v…..k)+(k….x),那说明到k的路径比到x短嘛,所以说如果选的话,也是k被选上咯,轮不上你x。so….就是个这么玩意儿,脑子卡了有一会儿。
  好,第一个费解点已经过了,下面走在去第二个费解点的路上 o(╥﹏╥)o。比较两种算法,我发现Floyd算法实现起来比较简单,然后就用它实现了交上去,结果好像是运行超时,45分。然后我就改用了dijkstra,当然图的存储结构还用的是二维数组,提交结果是运行错误,50分。就是这个该死的“运行错误”,到昨天晚上出实验室的前十分钟,我都没有弄明白为什么是运行错误。卡壳一下午。一度怀疑这个问题能不能用最短路径算法来求解。然后套用上面的正确性证明,到x的路径可以分为(v…..k)和(k….x),那么dis[x]’=Max(dis[x],dis[k]’,Max(k…x)) ,dis[x]’为v到x新的最短距离(此题中“最短距离”的含义为:一条路径上,所有段中天数的最大值),dis[x]是之前的,dis[k]’是(v…..k)段上最短距离,Max(k…x)指的是k到x所有段中的最大的那个数值。如果只考虑经过k的这条路径的话,那么结果得到的dis[x]会大于等于dis[k]。问题就出现在这个“等于”上, 既然k点的数值和x点的可能相等,那么选择的时候也可能选k点,而不是x点。仔细考虑下,这个“等于”的情况对最后结果应该也没有影响的,只能说明到目标点有两条或者多条长度相等的最短路径(以上证明我今天才想清楚了些,昨天还是糊涂的)。百度了下,虽然大多数人用的是最小生成树,但是也有用dijkstra做出来的,所以我放心地陷进了这个算法,思考着为啥我的dijkstra为啥就不行┭┮﹏┭┮。。。终于昨天晚上出实验室之前,灵光一现,发现很有可能是因为用的数据结构是二维数组,占内存太大。因为我看我的提交结果所占内存是256.8M,但是要求的是256M,因为天色已晚,我要保证自己的规律作息,所以回去了,打算今天一早回来试一下,当然回去了之后还是满脑子的正确性证明,翻来覆去。。。啊啊,归根结底,为啥你要提示“运行错误”啊,你提示“超出内存”不简单明了多了。。
  好了,时间终于到了今天,开始跳第三个坑ヘ(;´Д`ヘ)。一早上试了一下用邻接表(Adjacency List)来存储图结构,然而本地VS2013运行毫无问题,提交上去,秒回“编译错误”。各种百度,后来发现问题在于没有#include<malloc.h> 而且,

struct ArcNode{
    int adjvex;
    ArcNode *NextArc;
      };

在VS里完全可以,然而到dev-c++编译器里面就会报错,应该写成这样

struct ArcNode{
    int adjvex;
    Struct ArcNode *NextArc;
      };

改完这些之后,提交上去,运行超时,80分。终于和别人的dijkstra算法的80分一样了(真正的起点应该在这里啊啊啊啊,哭晕~)。后来搜了一下,说是要用最小堆优化。下午吭哧吭哧在理解最小堆,不知道要怎么建立最小堆,怎么自己实现。后来用STL自带的priority_queue 实现的。参考的是http://blog.csdn.net/eternity666/article/details/68974954 的做法。提交,结果90分,始终不理解,因为上面那篇能得95。终于吃完晚饭回来,想到一个小的改进之处可以加进来(这个想法是在没有用最小堆的时候用的,但是实现最小堆之后没有加进去),也就是当n点被标记完毕,就不再找了,因为没有这个必要了,dijkstra的完整算法是能找到一个源点到其他所有点的最短路径,我们不必找到所有的,所以当找到到n的之后就不再找了,提交,正确,一百分。 ヽ( ̄▽ ̄)ノ终于。。。。。哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

此处是分界线,以下为干货

题目
试题编号:   201703-4
试题名称:   地铁修建
时间限制:   1.0s
内存限制:   256.0MB
问题描述:   
  A市有n个交通枢纽,其中1号和n号非常重要,为了加强运输能力,A市决定在1号到n号枢纽间修建一条地铁。
  地铁由很多段隧道组成,每段隧道连接两个交通枢纽。经过勘探,有m段隧道作为候选,两个交通枢纽之间最多只有一条候选的隧道,没有隧道两端连接着同一个交通枢纽。
  现在有n家隧道施工的公司,每段候选的隧道只能由一个公司施工,每家公司施工需要的天数一致。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。
  作为项目负责人,你获得了候选隧道的信息,现在你可以按自己的想法选择一部分隧道进行施工,请问修建整条地铁最少需要多少天。
输入格式
  输入的第一行包含两个整数n, m,用一个空格分隔,分别表示交通枢纽的数量和候选隧道的数量。
  第2行到第m+1行,每行包含三个整数a, b, c,表示枢纽a和枢纽b之间可以修建一条隧道,需要的时间为c天。
输出格式
  输出一个整数,修建整条地铁线路最少需要的天数。
样例输入
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
样例输出
6
样例说明
  可以修建的线路有两种。
  第一种经过的枢纽依次为1, 2, 3, 6,所需要的时间分别是4, 4, 7,则整条地铁线需要7天修完;
  第二种经过的枢纽依次为1, 4, 5, 6,所需要的时间分别是2, 5, 6,则整条地铁线需要6天修完。
  第二种方案所用的天数更少。
评测用例规模与约定
  对于20%的评测用例,1 ≤ n ≤ 10,1 ≤ m ≤ 20;
  对于40%的评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 1000;
  对于60%的评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 10000,1 ≤ c ≤ 1000;
  对于80%的评测用例,1 ≤ n ≤ 10000,1 ≤ m ≤ 100000;
  对于100%的评测用例,1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,1 ≤ a, b ≤ n,1 ≤ c ≤ 1000000。
  所有评测用例保证在所有候选隧道都修通时1号枢纽可以通过隧道到达其他所有枢纽。
完整代码
#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
struct ArcNode{
    int adjvex;
    struct ArcNode *nextArc;
    int days;
};
struct vNode{
    int index;
    int dis;
    bool vis;
    struct ArcNode *firstArc;
    bool operator < (const vNode &t) const{
        return dis>t.dis;
    }
};
int main()
{
    int n, m;
    int a, b, c;
    /*FILE* stream;
    freopen_s(&stream, "in.txt", "r", stdin);*///输入流重定向到文件流,方便本地测试的时候用
    cin >> n >> m;
    vNode *NodeList = new vNode[n];
    for (int i = 0; i < n; i++)
    {
        NodeList[i].index = i;
        NodeList[i].dis = INF;
        NodeList[i].vis = false;
        NodeList[i].firstArc = NULL;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        if (NodeList[a - 1].firstArc == NULL){
            ArcNode *new_node = (ArcNode *)malloc(sizeof(ArcNode));
            new_node->adjvex = b - 1;
            new_node->nextArc = NULL;
            new_node->days = c;
            NodeList[a - 1].firstArc = new_node;
        }
        else{
            ArcNode *p = NodeList[a - 1].firstArc;
            while (p->nextArc != NULL)
            {
                p = p->nextArc;
            }
            ArcNode *new_node = (ArcNode *)malloc(sizeof(ArcNode));
            new_node->adjvex = b - 1;
            new_node->nextArc = NULL;
            new_node->days = c;
            p->nextArc = new_node;
        }
        if (NodeList[b - 1].firstArc == NULL){
            ArcNode *new_node = (ArcNode *)malloc(sizeof(ArcNode));
            new_node->adjvex = a - 1;
            new_node->nextArc = NULL;
            new_node->days = c;
            NodeList[b - 1].firstArc = new_node;
        }
        else{
            ArcNode *p = NodeList[b - 1].firstArc;
            while (p->nextArc != NULL)
            {
                p = p->nextArc;
            }
            ArcNode *new_node = (ArcNode *)malloc(sizeof(ArcNode));
            new_node->adjvex = a - 1;
            new_node->nextArc = NULL;
            new_node->days = c;
            p->nextArc = new_node;
        }
    }//初始化
    priority_queue<vNode> heap;
    NodeList[0].dis = 0; //NodeList[0].vis = true;
    heap.push(NodeList[0]);
    int k = 0;
    vNode temp;
    while (!heap.empty())
    {
        temp = heap.top();
        heap.pop();
        int u = temp.index;
        if (NodeList[u].vis)
        {
            continue;
        }
        NodeList[u].vis = true;
        ArcNode *q = NodeList[u].firstArc;
        while (q != NULL)
        {
            int max = (NodeList[u].dis > q->days) ? NodeList[u].dis : q->days;
            if (!NodeList[q->adjvex].vis&&max < NodeList[q->adjvex].dis)
            {
                NodeList[q->adjvex].dis = max;
                heap.push(NodeList[q->adjvex]);
            }
            q = q->nextArc;
        }
        if (NodeList[n-1].vis)
        {
            break;
        }
    }
    //下面是没有用最小堆优化时的算法
    /*ArcNode *q = NodeList[0].firstArc;
    while (q != NULL)
    {
    NodeList[q->adjvex].dis = q->days;
    q = q->nextArc;
    }
    while (k != n - 1) //找到到n-1这个节点的最短路径就不再往下继续找了
    {
        int min = INF;
        for (int j = 0; j < n; j++)
        {
            if (!NodeList[j].vis)
            {
                if (NodeList[j].dis < min)
                {
                    min = NodeList[j].dis;
                    k = j;
                }
            }
        }
        NodeList[k].vis = true;
        ArcNode *q = NodeList[k].firstArc;
        while (q != NULL)
        {
            int max = (min > q->days) ? min : q->days;
            if (max < NodeList[q->adjvex].dis)
            {
                NodeList[q->adjvex].dis = max;
            }
            q = q->nextArc;
        }
    }*/
    cout << NodeList[n - 1].dis << endl;
    delete[]NodeList;
    return 0;
}

至此,去看《那年花开月正圆》了~

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹