`
暴风雪
  • 浏览: 388859 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[双连通分量+队列优化dijkstra]acdream 1415

 
阅读更多

题意:

       给出一个n个点,m条边无向图(2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000).。求出存在哪些边,使得去掉这些边之后,最短路的长度会增加。

 

思路:

       第一步求出最短路,并判断出哪些边可以在最短路上。并用这些边重新建图。

       第二步,用第一步建出的图求出割边,得到的割边就是答案

       要注意tarjan时可能会出现重边

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int nMax=20050;
const int mMax=400005 ;
const long long inf= 1e18 ;

struct{
    int u,v, next;
    int  w;
    int num;
}edge[mMax],edge1[mMax];
int n,k, head[nMax],head1[nMax],k1;
int que[nMax];
bool vis[nMax];

void addedge(int a,int b,int w,int num){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].num=num;
    edge[k].next=head[a];
    head[a]=k;k++;
}
void addedge1(int a,int b,int num){
    edge1[k1].u=a;
    edge1[k1].v=b;
    edge1[k1].num=num;
    edge1[k1].next=head1[a];
    head1[a]=k1;k1++;
}


struct node{
    int u;
    long long dis;
    bool operator < (const node &a) const{        //  heap的重载 < 号的形式。
        return dis > a.dis;
    }
};
void dijkstra(int s ,long long dis[nMax]){
    for(int i = 1; i <= n; i ++){
        dis[i] = inf;
        vis[i] = false;
    }
    dis[s] = 0;
    priority_queue<node> que;    //  运用STL的优先队列。
    node a;
    a.u = s; a.dis = 0;
    que.push(a);
    while(!que.empty()){
        int u = que.top().u;
        que.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(!vis[v] && dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                a.u = v; a.dis = dis[v];
                que.push(a);
            }
        }
    }
}
long long dis[nMax];
long long dis1[nMax];

int dep,nbridge;
int dfn[nMax],low[nMax],res[mMax];

void Tarjan(int u,int fa){                        //我的割边模版
    dfn[u]=low[u]=++dep;
    int flag = 1 ;
    for(int i=head1[u];i;i=edge1[i].next){
        int v=edge1[i].v;
        if ( v == fa && flag ) {
            flag = 0 ;
            continue ;
        }
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
               res[++nbridge]=edge1[i].num;
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main(){
    int i,m,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF){
        k=1;
        memset(head,0,sizeof(head));
        k1=1;
        memset(head1,0,sizeof(head1));


        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c,i);
            addedge(b,a,c,i);
        }

        dijkstra(1,dis);
        dijkstra(n,dis1);
        for(i=1;i<k;i++){
            int u=edge[i].u;
            int v=edge[i].v;
            if(dis[u]+edge[i].w+dis1[v]==dis[n]||dis[v]+edge[i].w+dis1[u]==dis[n]){
                addedge1(u,v,edge[i].num);
            }
        }

        dep=0;
        nbridge=0;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        for(i=1;i<=n;i++)if(!dfn[i])Tarjan(i,-1);

        printf("%d\n",nbridge);
        if(nbridge){
            for(i=1;i<nbridge;i++){
                printf("%d ",res[i]);
            }printf("%d\n",res[nbridge]);
        }
    }
    return 0;
}

 

1
1
分享到:
评论

相关推荐

    毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip

    毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip主要针对计算机相关专业的正在做课程设计和期末大作业的学生和需要项目实战练习的学习者。包含全部项目源码、该项目可以直接使用、项目都经过...

    毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统

    毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...

    基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip

    1、基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip 2、该资源包括项目的全部源码,下载可以直接使用! 3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...

    堆优化的dijkstra算法(dijkstra+邻接表+heap)

    在处理大规模数据时,原始的Dijkstra算法的时间复杂度较高,通常采用优先队列进行优化,即堆优化的Dijkstra算法。本篇文章将详细介绍如何利用邻接表和最小堆来实现Dijkstra算法,并分析其时间复杂度和空间复杂度。 ...

    基于springboot+mysql+Dijkstra算法实现物流优化管理系统完整源码+说明(课程设计).zip

    【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能正常的情况下才上传的,请放心下载使用。 2、适用人群:主要针对计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、...

    Dijkstra最短路径算法的优化及其实现

    ### Dijkstra最短路径算法的优化及其实现 #### 一、引言 随着计算机网络技术和地理信息科学的发展,最短路径问题无论是在交通运输、城市规划、物流管理、网络通讯等方面,都发挥了重要的作用。因此,对最短路径...

    dijkstra算法(C++实现)

    在C++中实现这个算法,我们可以利用STL中的优先队列数据结构,例如`std::priority_queue`来优化效率。 Dijkstra算法的基本思想是使用贪心策略,每次选择当前未访问节点中距离源节点最近的一个,将其加入到已访问...

    堆优化dijkstra.cpp

    堆优化dijkstra算法。使用邻接表。邻接表的应用案例。 Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra...

    堆优化dijkstra代码模板示例

    dijkstra时间优化,堆优化,优先队列,最短路算法,O(NlogN)空间时间优化,链式存储,邻接表存图,NOIP,ACM算法竞赛,数据结构

    求一个Dijkstra优化算法.rar_c++求最短距离_dijkstra_dijkstra+ 优化_最短距离_最短路径

    在C++中实现Dijkstra算法,主要是利用优先队列(如二叉堆)来实现最小元素的选择,以及动态更新节点的最短距离。在给定的压缩包文件中,"求一个Dijkstra优化算法.doc"可能是对Dijkstra算法的详细解释或优化后的代码...

    堆优化Dijkstra.exe

    堆优化Dijkstra.exe

    Dijkstra+STL(优化)(速度很快,不多说)

    在本示例中,Dijkstra算法结合了C++的STL(Standard Template Library)库,以优化算法的实现,提高运行效率。 首先,我们来看一下代码中的关键部分。`#define`预处理器指令用于定义常量,如N表示顶点的最大数量,M...

    代码 基于最短路dijkstra算法离散优化问题代码

    代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...

Global site tag (gtag.js) - Google Analytics