标签：连通 add 判断 printf -- 有向无环图 包含 hellip dijstra
说在前面
首先这题单纯从数据出发的话，直接做SPFA，加点优化，SLF或者LLL的话是可以直接过的。
但是，本着科学严谨的态度，极其不推荐使用这种投机取巧的偷懒方式。而且如果数据是特殊构造的话，就算加了优化也一样会被卡。故此处介绍正解。
算法介绍
算法描述：
考虑到本题有个非常好的性质：有向边必然无环。
先不考虑有向边，则所有无向边加点集构成的图就是数个连通块。
考虑有向边，将每个连通块看成点，每条有向边就是这些点之间的连边，则整张图构成一张有向无环图，可以直接拓扑排序遍历。
对于每个连通块内部，直接做Dijkstra即可。
算法流程：
先读入无向边，然后处理连通块，记录每个点所属的连通块编号以及每个连通块所包含的所有点。
再读入有向边，记录每个连通块的入度。
先找到入度为0的连通块，然后开始拓扑排序。
对于遍历到的每一个连通块，做一遍Heap_Dijkstra。在进行松驰操作时，判断两点是否在同一个连通块内，若是，则将其放入Heap中，否则将所指向的点所属连通块入度减1，然后将其放入拓扑队列中即可。
时间复杂度分析：
连通块处理和拓扑排序都是线性的，整个算法时间上的瓶颈就在于Dijkstra。
设连通块x内点数为nx，边数为mx。
则所有Dijstra的总时间为：m1logn1+m2logn2+……+mslogns
故整个算法时间复杂度为O(N+MlogN)，效率非常高。
参考代码：
1 #include 2 #include 3 #include
4 #include 5 #include 6 using namespace std;
7 const int N=3e4+10,M=5e4+10,INF=0x3f3f3f3f;
8 struct Edge{
9 int to,ne,w;
10 }edge[M2]; int idx;
11 int h[N];
12 int n,m1,m2,s;
13 int dis[N],vis[N];
14 int cnt_block;
15 int id[N],ind[N];
16 vectorint> block[N];
17 queueint> q;
18
19 void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;}
20
21 void dfs(int u,int id_block)
22 {
23 vis[u]=1;
24 id[u]=id_block;
25 block[id_block].push_back(u);
26
27 for(int i=h[u];~i;i=edge[i].ne)
28 {
29 int to=edge[i].to;
30 if(!vis[to])dfs(to,id_block);
31 }
32
33 }
34
35 void dijkstra(int b)
36 {
37 priority_queueint,int> > heap;
38
39 int sz=block[b].size();
40 for(int i=0;i)
41 heap.push(make_pair(-dis[block[b][i]],block[b][i]));
42
43 while(!heap.empty())
44 {
45 int k=heap.top().second;
46 heap.pop();
47
48 if(vis[k])continue;
49 vis[k]=1;
50
51 for(int i=h[k];~i;i=edge[i].ne)
52 {
53 int to=edge[i].to,w=edge[i].w;
54 if(dis[to]>dis[k]+w)
55 {
56 dis[to]=dis[k]+w;
57 if(id[k]==id[to])heap.push(make_pair(-dis[to],to));
58 }
59 if(id[k]!=id[to]&&--ind[id[to]]==0)q.push(id[to]);
60 }
61 }
62 }
63
64 void topo_sort()
65 {
66 memset(dis,0x3f,sizeof dis);
67 memset(vis,0,sizeof vis);
68 dis[s]=0;
69
70 for(int i=1;i)
71 if(!ind[i])q.push(i);
72
73 while(!q.empty())
74 {
75 int k=q.front();
76 q.pop();
77
78 dijkstra(k);
79 }
80 }
81
82 int main()
83 {
84 memset(h,-1,sizeof h);
85 scanf("%d%d%d%d",&n,&m1,&m2,&s);
86 while(m1--)
87 {
88 int a,b,c;
89 scanf("%d%d%d",&a,&b,&c);
90 add_edge(a,b,c);
91 add_edge(b,a,c);
92 }
93
94 for(int i=1;i)
95 if(!vis[i])dfs(i,++cnt_block);
96
97 while(m2--)
98 {
99 int a,b,c;
100 scanf("%d%d%d",&a,&b,&c);
101 add_edge(a,b,c);
102 ind[id[b]]++;
103 }
104
105 topo_sort();
106
107 for(int i=1;i)
108 {
109 if(dis[i]>INF/2)puts("NO PATH");
110 else printf("%d\n",dis[i]);
111 }
112
113 return 0;
114 }
题解——Acwing.342 道路与航线
标签：连通 add 判断 printf -- 有向无环图 包含 hellip dijstra
原文地址：https://www.cnblogs.com/ninedream/p/12208122.html