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

2017-09-14 08:05:21来源:CSDN作者:yulijuanxmu人点击

分享

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

做此题的心路历程

  咳咳,要开始讲了哇,因为我的蜗牛速度(对图的各种算法和基础的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 61 2 42 3 43 6 71 4 24 5 55 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 0x3f3f3f3fstruct 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;}

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

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台