题意:
给出一个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; }
相关推荐
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip主要针对计算机相关专业的正在做课程设计和期末大作业的学生和需要项目实战练习的学习者。包含全部项目源码、该项目可以直接使用、项目都经过...
1、基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip 2、该资源包括项目的全部源码,下载可以直接使用! 3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...
毕设基于springboot+thyemleaf的超市管理系统源码.zip毕设基于springboot+thyemleaf的超市管理系统源码.zip毕设基于springboot+thyemleaf的超市管理系统源码.zip毕设基于springboot+thyemleaf的超市管理系统源码.zip...
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能正常的情况下才上传的,请放心下载使用。 2、适用人群:主要针对计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、...
堆优化dijkstra算法。使用邻接表。邻接表的应用案例。 Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra...
转一个Dijks tra最短路径算法,很好的一个算法
用C++实现的dijkstra算法,代码可以通用
matlab算法,毕设、课设程序,全部源码均已进行严格测试,可以直接运行! matlab算法,毕设、课设程序,全部源码均已进行严格测试,可以直接运行! matlab算法,毕设、课设程序,全部源码均已进行严格测试,可以直接...
dijkstra时间优化,堆优化,优先队列,最短路算法,O(NlogN)空间时间优化,链式存储,邻接表存图,NOIP,ACM算法竞赛,数据结构
用堆优化的dijkstra,接口为邻接链表。
堆优化Dijkstra.exe