题解——Acwing.342 道路与航线

说在前面

  首先这题单纯从数据出发的话,直接做SPFA,加点优化,SLF或者LLL的话是可以直接过的。

  但是,本着科学严谨的态度,极其不推荐使用这种投机取巧的偷懒方式。而且如果数据是特殊构造的话,就算加了优化也一样会被卡。故此处介绍正解。

算法介绍

算法描述:

  考虑到本题有个非常好的性质:有向边必然无环。
  先不考虑有向边,则所有无向边加点集构成的图就是数个连通块。
  考虑有向边,将每个连通块看成点,每条有向边就是这些点之间的连边,则整张图构成一张有向无环图,可以直接拓扑排序遍历。
  对于每个连通块内部,直接做Dijkstra即可。

算法流程:

  先读入无向边,然后处理连通块,记录每个点所属的连通块编号以及每个连通块所包含的所有点。
  再读入有向边,记录每个连通块的入度。
  先找到入度为0的连通块,然后开始拓扑排序。
  对于遍历到的每一个连通块,做一遍Heap_Dijkstra。在进行松驰操作时,判断两点是否在同一个连通块内,若是,则将其放入Heap中,否则将所指向的点所属连通块入度减1,然后将其放入拓扑队列中即可。

时间复杂度分析:

  连通块处理和拓扑排序都是线性的,整个算法时间上的瓶颈就在于Dijkstra。
  设连通块x内点数为nx,边数为mx。
  则所有Dijstra的总时间为:m1logn1+m2logn2+……+mslogns<=m1logN+m2logN+……+mslogN=(m1+m2+……+ms)logN=MlogN。
  故整个算法时间复杂度为O(N+MlogN),效率非常高。

参考代码:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <vector>
  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[M<<2]; 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 vector<int> block[N];
 17 queue<int> 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_queue<pair<int,int> > heap;
 38     
 39     int sz=block[b].size();
 40     for(int i=0;i<sz;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<=cnt_block;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<=n;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<=n;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 道路与航线

上一篇:C# Font类


下一篇:C#-特性,反射,动态编程