Roads and Planes

2023-12-28 11:15:28

A 前言

（本文搬运自作者学校WordPress中 作者所写文章）

对于2020.8.5日的C2022同学们

这题有yi点超纲，

所以，里面会涉及到一些新的概念，新的知识

预计里面的概念在2020.8.6日我们可以全面掌握

所以不再题解中过多对概念进行诠释

同时，陈同学讲解的SPFA的SLF优化是可以水过的，但并不是本题的正解

正解oj上用时200ms

而加了SLF的SPFA还是用了1500ms勉强卡过（时限2s）

Roads and Planes

Roads and Planes

B 题面

Roads and PlanesRoads and Planes

C 解题

我们把题目稍微概括一下：

有 T 个点，R 条双向边，P 条单向边。其中双向边权值均为正，单向边权值可以为负。

保证如果有一条航线可以从 a 到 b，那么保证不可能通过一些道路和航线从 b 回到 a。

请你求出 S 到所有点的最短距离，若不能到达则输出"NO PATH"

数据范围： 1<=T<=25000 , 1<=R,P<=50000

容易发现，这是一个带负权的最短路

乍一看，我们可以用SPFA（关于SPFA，它死了！！！），但显然会被卡掉

而考虑dijkstra又会有负权的问题

所以我们需要从题目中挖掘一些特别的性质来解决这道题

我们把题目在读一遍，看到这样一句话：

保证如果有一条航线可以从 a 到 b，那么保证不可能通过一些道路和航线从 b 回到 a

也就是说：

这个图不存在负环，有可能存在正环

也就是说，如果只把双向边添加进来，那么一定就形成了若干个强连通的块。

或者是说，我们可以把双向边连接的点看作是一个整体

（不知道强联通的看 ）

图片理解：（图丑轻喷）

Roads and Planes

这其实运用到了缩点（了解更多）

而可能的负权边又保证不成环（不反向联通）

因此把无向边联通块缩点后，得到的就是有向无环图

所以，我们可以在块内使用dijkstra最短路

块间利用拓扑排序更新答案

（在这里我假设我们知道拓扑排序 实在不知道看 这里）

为什么要用拓扑排序呢？

  • 拓扑排序可以处理负边权
  • 拓扑排序时间复杂度是O（V+E）
  • 拓扑排序得到的路径显然就是答案

（注：拓扑排序的缺点在于要求出发点入度为0，终点出度为0 且 不能处理无向边）

C1 定义

由于本题变量实在太多，所以我把它们定义在一起，

方便大家看到后面突然对变量名迷茫了 可以回头看一看

（自认为变量名含义还是比较明了的）

const int N=25003,M=150003,INF=0x3f3f3f3f;
struct Edge{
    int next;   //下一条边 
    int dis;    //边权 
    int to;     //下一个点 
}edge[M];
int t,r,p,s,elen;   //t个点，r条双向边，p条单向边，起点s，edge[]长度elen 
int head[N];        //head[i]是i的第一条边 
int id[N];          //id[i]是i点所在的联通块编号 
int dis[N];         //dis[i]是i点到起点的最短路 
int vis[N];         //i是否被访问过 
int in[N];          //in[i]是i点拓扑排序的入度 
queue<int>q;        //拓扑排序的队列 
vector<int>block[N];//block[i]存联通块i中的点 
int cnt_block;      //联通块的个数

dijkstra

（我在这里是使用的STL，了解更多 ）

（背不住dijkstra模板的可以劝退了）

  • 将每一个点插入堆中
  • 取出堆中的最小值，遍历与那个点相连的点（优先队列实现）
  • 如果可以更新最短距离，就更新；并且如果它们处于同一个连通块中，就将遍历到的点插入堆中。
  • 如果它们不在同一个联通块里面，且遍历到的点入度为0，则将这个点插入拓扑排序的队列里

我们一步步来：

1.定义一个优先队列：

priority_queue <pair <int ,int > > qh;

同时需要说明的的是：其实优先队列是实现堆实现的，默认是大根堆

所我们可以把它理解成堆的STL

第一个排序依据是pair的first

第二个排序依据是pair的second。

第一关键字是距离 dis[i]

第二关键字自然是 i

2.将每一个点插入堆中

int len=block[now].size();            //.size()获得block[i]的长度 
for(int i=0;i<len;i++){
    qh.push(make_pair(-dis[block[now][i]],block[now][i]));//将每一个点插入队列中 
}

ph.push(a)表示把a插入队列

make_pair(a,b)表示生成数据

值得注意的是，因为这默认是大根堆

而我们需要的是小根堆，所以我们可以通过加个符号的方法

让他实际上是一个小根堆

（其实所谓“默认”是可以调整的，可以见袁同学的 15分钟掌握STL）

3.取出堆中的最小值，遍历与那个点相连的点

while(!qh.empty()){                     //堆不空 
    int u=qh.top().second;              //其实取出的是最小值的位置 
    qh.pop();                           //取出后要把堆顶删除（弹出）
    if(vis[u])continue;                 //跳过 
    vis[u]=1;                           //标记 
    for(int e=head[u];e;e=edge[e].next){//遍历边
        //do the other things...
    }
}

qh.second是pair中第二个值

4.如果可以更新最短距离，就更新；并且如果它们处于同一个连通块中，就将遍历到的点插入堆中

这里其实是对for循环内语句的描述

（忘记变量名意思的可以回头看一眼）

int v=edge[e].to;
if(dis[v]>dis[u]+edge[e].dis){ //可以更新距离 
    dis[v]=dis[u]+edge[e].dis;
    if(id[v]==id[u])           //在同一个联通块中 
        qh.push(make_pair(-dis[v],v));//插入堆 
    
}

注意默认是大根堆

5.如果它们不在同一个联通块里面，且遍历到的点入度为0，则将这个点插入拓扑排序的队列里

也就是：

if(id[v]!=id[u]&&!--in[id[v]])q.push(id[v]);

我们把上述代码串起来：

inline void dijkstra(int now){
    priority_queue <pair <int ,int > > qh;//定义一个优先队列 
    int len=block[now].size();            //.size()获得block[i]的长度 
    for(int i=0;i<len;i++){
        qh.push(make_pair(-dis[block[now][i]],block[now][i]));//将每一个点插入堆中 
    }
    while(!qh.empty()){                         //堆不空 
        int u=qh.top().second;              //其实取出的是最小值的位置 
        qh.pop();                           //取出后要把堆顶删除（弹出） 
        if(vis[u])continue;                 //跳过 
        vis[u]=1;                           //标记 
        for(int e=head[u];e;e=edge[e].next){//遍历边 
            int v=edge[e].to;
            if(dis[v]>dis[u]+edge[e].dis){ //可以更新距离 
                dis[v]=dis[u]+edge[e].dis;
                if(id[v]==id[u])       //在同一个联通块中 
                    qh.push(make_pair(-dis[v],v));//插入堆 
            }
            if(id[v]!=id[u]&&!--in[id[v]])q.push(id[v]);
//下一个块可以进行拓扑排序
        }
    }
}

其他

拓扑排序

inline void toposort(){               //拓扑排序 
    memset(dis,0x3f,sizeof(dis)); //初始化最短距离 
    dis[s]=0;
    for(int i=1;i<=cnt_block;i++){//cnt_block:块的个数 
        if(!in[i])q.push(i);      //先加入入度为0 的点 
    }
    while(!q.empty()){            //非空 
        int t=q.front();q.pop(); //取出第一个点并弹出 
        dijkstra(t);             //对每个联通块做dijkstra 
    }
}

拓扑排序的定义：

如果a排在b前面，则b不能通过任何方式到达a

为了适应本题需要，上面代码并不是拓扑排序的模板

下面给出拓扑排序的伪代码模板：

  1. 数据结构：inder[i]顶点i的入度，stack[] 栈
  2. 初始化：top=0（栈顶指针置零）
  3. i=0（计数器）
  4. while(栈非空）
    • 栈顶顶点v出栈;top-1;输出v；i++；
    • for v的每一个后继顶点u
      1. inder[i]--; u的入度减1
      2. if indet[i]==0 顶点 u 入栈

可以据此帮助理解上面的内容

 

DFS求id[]

void dfs(int u,int nowid){
    id[u]=nowid;
    block[nowid].push_back(u);
    for(int e=head[u];e;e=edge[e].next){
        int v=edge[e].to;
        if(!id[v])dfs(v,nowid);
    }
}

注意id[i]表示i点所在的联通块的编号

 

建立边

这个就是常规操作了（邻接表建边）

inline void add(int from,int to,int dis){
    edge[++elen].next=head[from];
    edge[elen].to=to;
    edge[elen].dis=dis;
    head[from]=elen;
}

 

main函数

在本题中，尤其需要注意上述函数的执行位置和顺序，比如：

dfs函数必须在单项边输入前执行，因为联通块中不含单向边

当然不只这一个细节

int main(){
    scanf("%d%d%d%d",&t,&r,&p,&s);
    for(int i=1;i<=r;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=t;i++){//求每个点所在的联通块编号 
        if(!id[i]){
            cnt_block++;
            dfs(i,cnt_block);
        }
    }
    for(int i=1;i<=p;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        in[id[v]]++;//统计入度 
    }
    toposort();//拓扑排序 
    for(int i=1;i<=t;i++){
        if(dis[i]>INF/2)printf("NO PATH\n");//判无解 
        else printf("%d\n",dis[i]);
    }
    return 0;
}

注意判误解的要求是inf/2

这是为了判断无法到达时还用负数去更新的情况

D 代码

Roads and Planes
#include<bits/stdc++.h>
using namespace std;
const int N=25003,M=150003,INF=0x3f3f3f3f;

struct Edge{
    int next;       //下一条边 
    int dis;        //边权 
    int to;         //下一个点 
}edge[M];
int t,r,p,s,elen;   //t个点，r条双向边，p条单向边，起点s，edge[]长度elen 
int head[N];        //head[i]是i的第一条边 
int id[N];          //id[i]是i点所在的联通块编号 
int dis[N];         //dis[i]是i点到起点的最短路 
int vis[N];         //i是否被访问过 
int in[N];          //in[i]是i点拓扑排序的入度 
queue<int>q;        //拓扑排序的队列 
vector<int>block[N];//block[i]存联通块i中的点 
int cnt_block;      //联通块的个数 

inline void add(int from,int to,int dis){
    edge[++elen].next=head[from];
    edge[elen].to=to;
    edge[elen].dis=dis;
    head[from]=elen;
}

void dfs(int u,int nowid){
    id[u]=nowid;
    block[nowid].push_back(u);
    for(int e=head[u];e;e=edge[e].next){
        int v=edge[e].to;
        if(!id[v])dfs(v,nowid);
    }
}

inline void dijkstra(int now){
    priority_queue <pair <int ,int > > qh;//定义一个优先队列 
    int len=block[now].size();            //.size()获得block[i]的长度 
    for(int i=0;i<len;i++){
        qh.push(make_pair(-dis[block[now][i]],block[now][i]));//将每一个点插入堆中 
    }
    while(!qh.empty()){                     //堆不空 
        int u=qh.top().second;              //其实取出的是最小值的位置 
        qh.pop();                           //取出后要把堆顶删除（弹出） 
        if(vis[u])continue;                 //跳过 
        vis[u]=1;                           //标记 
        for(int e=head[u];e;e=edge[e].next){//遍历边 
            int v=edge[e].to;
            if(dis[v]>dis[u]+edge[e].dis){ //可以更新距离 
                dis[v]=dis[u]+edge[e].dis;
                if(id[v]==id[u])           //在同一个联通块中 
                    qh.push(make_pair(-dis[v],v));//插入堆 
            }
            if(id[v]!=id[u]&&!--in[id[v]])q.push(id[v]);
                                           //下一个块可以进行拓扑排序 
        }
    }
}

inline void toposort(){           //拓扑排序 
    memset(dis,0x3f,sizeof(dis)); //初始化最短距离 
    dis[s]=0;
    for(int i=1;i<=cnt_block;i++){//cnt_block:块的个数 
        if(!in[i])q.push(i);      //先加入入度为0 的点 
    }
    while(!q.empty()){            //非空 
        int t=q.front();q.pop(); //取出第一个点并弹出 
        dijkstra(t);             //对每个联通块做dijkstra 
    }
}

int main(){
    scanf("%d%d%d%d",&t,&r,&p,&s);
    for(int i=1;i<=r;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=t;i++){//求每个点所在的联通块编号 
        if(!id[i]){
            cnt_block++;
            dfs(i,cnt_block);
        }
    }
    for(int i=1;i<=p;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        in[id[v]]++;//统计入度 
    }
    toposort();//拓扑排序 
    for(int i=1;i<=t;i++){
        if(dis[i]>INF/2)printf("NO PATH\n");//判无解 
        else printf("%d\n",dis[i]);
    }
    return 0;
}
View Code

 

上一篇：MySQL数据库服务端的启动及配置文件


下一篇：终于安装上TensorFlow了，孩子泪目