北航软件算法C4--图部分

🕗 发布于 2024-11-19 22:33 算法

TOPO!

在这里插入图片描述

步骤

这道题比较简单，因为是要从大到小输出，所以用队列的时候，用上大根堆。（还记得建小堆怎么建吗？）

priority_queue<int,vector< int >,greater< int >> heap;

三个参数都不能少哈↑
构建大根堆只需写 priority_queue< int >

如果没说顺序，那么可以用y总的手搓队列。

代码段

int e[N],ne[N],idx,h[N];
/*
e[i]表示第i个点的值，
ne[i]表示第i个点的next点的下标（编号
h[a]是值为a的点指向的点的下标）
*/
int n,m;
int dgr[N];//dgr[i]表示值为i的点对应的下标
//注意一定是值，不是编号，
int toposort[N];//存放排序结果
int INDEX;

TOPO排序部分

void topo(){
    priority_queue<int> heap;//如果没说要按什么顺序输出，那普通的队列就可以
    for(int i=1;i<=n;i++){
        if(dgr[i]==0){
            heap.push(i);//先把所有入度为0的点全部放进去
        }
    }
    
    while(!heap.empty()){
        int top = heap.top();
        heap.pop();
        toposort[INDEX++]=top;//取堆顶
        for(int i=h[top];i!=-1;i=ne[i]){//把堆顶点连着的点全部都遍历一遍，所有点的入度都减一，如果他变为0了，那么入堆
            int val = e[i];
            dgr[val]--;
            if(dgr[val]==0){
                heap.push(val);
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<toposort[i]<<' ';
    }
}

完整代码

#include <iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e6+3;
int e[N],ne[N],idx,h[N];
int n,m;
int dgr[N];
int toposort[N];//存放排序结果
int INDEX;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void topo(){
    priority_queue<int> heap;
    for(int i=1;i<=n;i++){
        if(dgr[i]==0){
            heap.push(i);
        }
    }
    
    while(!heap.empty()){
        int top = heap.top();
        heap.pop();
        toposort[INDEX++]=top;
        for(int i=h[top];i!=-1;i=ne[i]){
            int val = e[i];
            dgr[val]--;
            if(dgr[val]==0){
                heap.push(val);
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<toposort[i]<<' ';
    }
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        dgr[b]++;
    }
    topo();
}

简单的图图

题目描述

在这里插入图片描述

输入输出

在这里插入图片描述

样例

在这里插入图片描述

步骤

求多源最短路径，那就是Floyd算法了。
这道题只需要求u到v的最短路径长度，而不需要输出对应的路径序列，因此我们并不需要再开辟path数组，只需要开辟dist数组即可。

path数组用来存放经过的路径，可以用vector开辟一个存放String的二维数组
vector<vector< string >> strings(rows);//rows代表你想开辟的行数

代码段

开辟vector容器作为dist二维数组

vector<vector<ll>> dist(n+1,vector<ll>(n+1,INF));

后面的参数表示有n+1行，每一行是一个vector容器，每个元素初始化为INF最大值

初始化

for(int i=0;i<m;i++){
       ll u,v,w;
        cin>>u>>v>>w;
        dist[u][v]=min(dist[u][v],w);//因为有重边，则只保留值小的那一个
}
for(int i=1;i<=n;i++){
     dist[i][i]=0;
 }//对角线初始化为0

调用Floyd算法

for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dist[i][k]!=INF&&dist[k][j]!=INF)//注意这里要判断一下
                   dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }

查询

 int q;
    cin>>q;
    while(q--){
        ll u,v;
        cin>>u>>v;
        if(dist[u][v]==INF){
            cout<<-1<<endl;
        }else{
            cout<<dist[u][v]<<endl;
        }
    }

完整代码

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
//const int N = 305;
const long long  INF = 1e18;
int main(){
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> dist(n+1,vector<ll>(n+1,INF));
    for(int i=0;i<m;i++){
            ll u,v,w;
            cin>>u>>v>>w;
            dist[u][v]=min(dist[u][v],w);//因为有重边，则只保留值小的那一个
    }
    for(int i=1;i<=n;i++){
        dist[i][i]=0;
    }//对角线初始化为0
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dist[i][k]!=INF&&dist[k][j]!=INF)
                   dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    
    int q;
    cin>>q;
    while(q--){
        ll u,v;
        cin>>u>>v;
        if(dist[u][v]==INF){
            cout<<-1<<endl;
        }else{
            cout<<dist[u][v]<<endl;
        }
    }
}

负环

题目描述

在这里插入图片描述

输入输出

在这里插入图片描述

样例

在这里插入图片描述

步骤

先使用SPFA算法判断是否有负环，如果有负环，则输出“boo how”
要注意，用SPFA判断图内是否有负环的时候，负环不一定在起点到终点的路径上，因此开始初始化队列的时候，需要把所有的点都放进去。原理是：相当于给原图加上了一个虚拟源点，从该点向其他所有点都连着一条权为0的弧。cnt【x】等于n时，说明从x点到0点有n条边，即有n+1个点，而图内最多有n个点，由抽屉原理，在0-x的通路上，必然有两个相同的点。由于spfa每一次松弛操作，都让x到0距离变小，则必然存在负环
判断完负环以后，就可以再用一次spfa算法去计算每一个点到1号点的距离了。由于有负权边的存在，只能用spfa或者bellman——ford算法。
由于本题是多组数据输入，因此在每一次输出完数据之后，都要记得把该初始化的全都初始化干净。“打扫干净屋子再请客”。

代码段

全局变量定义

#define INF 1e9
const int N = 1e5;
const int M = 1e5;
ll e[M],ne[M],w[M],h[N],idx;//这几个数组，在编译器允许的范围内能开多大
int st[N];//判断第i个点是否在队里
//st数组设成bool类型也可
ll cnt[N],dist[N];//cnt数组记录第i个点到虚拟源点的最短路径的边数
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int n,m;

spfa1函数用于判断是否有负环

bool spfa1(){
    queue<int> q;

    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;
    }
    while(q.size()){
        auto top = q.front();
        q.pop();
        st[top]=0;
        for(int i=h[top];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[top]+w[i]){
                dist[j]=dist[top]+w[i];
                cnt[j]=cnt[top]+1;

                if(cnt[j]>=n){
                    return true;
                }
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return false;
}

spfa2用于记录每个点到1号点的距离

void sfpa2(){
    fill(dist,dist+N-1,INF);
    memset(st,0,sizeof st);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=1;

    while(q.size()){
        auto top = q.front();
        q.pop();
        st[top]=0;
        for(int i=h[top];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[top]+w[i]){
                dist[j]=dist[top]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }
    puts("");
}

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
#define INF 1e9
const int N = 1e5;
const int M = 1e5;
ll e[M],ne[M],w[M],h[N],idx;
int st[N];
ll cnt[N],dist[N];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int n,m;
bool spfa1(){
    queue<int> q;

    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;
    }
    while(q.size()){
        auto top = q.front();
        q.pop();
        st[top]=0;
        for(int i=h[top];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[top]+w[i]){
                dist[j]=dist[top]+w[i];
                cnt[j]=cnt[top]+1;

                if(cnt[j]>=n){
                    return true;
                }
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return false;
}
void sfpa2(){
    fill(dist,dist+N-1,INF);
    memset(st,0,sizeof st);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=1;

    while(q.size()){
        auto top = q.front();
        q.pop();
        st[top]=0;
        for(int i=h[top];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[top]+w[i]){
                dist[j]=dist[top]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }
    puts("");
}
int main(){
    int t;
    cin>>t;

    while(t--){
        cin>>n>>m;
        //该初始化的都一定一定要初始化，不然各组数据之间会串联
        memset(h,-1,sizeof h);
        memset(dist,0,sizeof dist);
        memset(cnt,0,sizeof cnt);
        memset(st,0,sizeof st);
        for(int i=0;i<m;i++){
            ll a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        if(spfa1()){
            cout<<"boo how"<<endl;
            continue;
        }else{
            sfpa2();
        }
    }
}

直击西溜线（地铁最短换乘次数）

题目描述

在这里插入图片描述

输入输出

在这里插入图片描述

样例

在这里插入图片描述

步骤

存储每次查询的起点和终点
存储每条线路的站点
存储每条线路站点的同时，将线路号加到map中每个站点对应的数组中（专门存放这个站点都属于哪些线路）
处理G【】【】邻接矩阵，用于表示每两条线路之间的换乘代价。初始化时，如果两条线之间没有直接换乘点，初始化为无穷；同一条线，初始化为0；有直接换乘点，初始化为1
用floyd算法计算每两条线路之间的最少换乘次数，更新G邻接矩阵
遍历每次查询的起点和终点，取它们所在的所有线路，找到换乘次数最小的两条线。
注意，最少换乘次数和最少乘坐站数不一样。最少换乘次数相当于把同一条线上抽象成了一个点，最少乘坐站数则直接用floyd或者dijikstra算法就可解决。

tip

输入需要用getline(cin,需要输入的内容） ,cin>>输入不能读取字符串之间的空格，而本题地铁站名含有空格。类似地，cin.get()可以用来接受单个字符，也可以接受带空格的字符串
由于getline（）读到回车就结束，如果输入整数之后，有回车，那么根本就不能正确获取地铁站名，例如：

>  int a;
>     string b;
>     cin>>a;
>     //cin.ignore();
>     getline(cin,b);
> 
>     cout<<a<<endl;
>     cout<<b<<endl;

如果不加cin.ignore()的话，geline读到a后面的回车就会直接结束输入的
除非你：

在这里插入图片描述这么输入。

访问vector()中的元素，如果没有提前给vector申请空间，那么不能直接用下标访问（这个一会儿结合具体代码说）

代码段

全局变量设定

const int INF = 1e9;
int G[30][30];//两条线路之间是否能换乘
//同一条线路，为0；不同线路可以直接换乘，为1；不同线路不能换乘，INF
vector<pair<string,string>> inquiries;//存放查询的起终点
map<string,vector<int>> mp;//存放每个站点属于哪些线路
vector<string> lines[30];//存放每条线路都有哪些站
int n,q;//地铁线路条数和询问次数

我们这里开辟inquiries和lines都是没有直接申请空间的，因此后面必须先用 resize(m) 给它申请m个空间，才能通过下标访问0-（m-1）的元素。

也可以直接：vector< string > lines（INF）；给它开辟INF个空间。二维vector数组初始化可以看看简单的图图那个题

完整代码

void least_change(){ 
    //将G图初始化为INF
    fill(G[0],G[0]+30*30,INF);

    cin>>n>>q;
    cin.ignore();
    inquiries.resize(q);
    for(int i=0;i<q;i++){
        getline(cin,inquiries[i].first);
        getline(cin,inquiries[i].second);
        //读取每次询问的起终点        
    }

    for(int i=0;i<n;i++){//读取每一条线路
        int m;
        cin>>m;
        cin.ignore();
        lines[i].resize(m);
        for(int j=0;j<m;j++){//读取每一条线路的每一个站
            getline(cin,lines[i][j]); 
            if(j==m-1&&(lines[i][m-1]==lines[i][0]))
                continue;                  
            mp[lines[i][j]].push_back(i);
        }
    }

   
    //同一线路上的站点，换乘代价为0
    for(int i=0;i<n;i++){
        G[i][i]=0;
    }

    //不同线路之间，是否能换乘，要手动判断
    for(auto station:mp){
        auto belongs = station.second;
        int sz = belongs.size();
        for(int i=0;i<sz;i++){
            for(int j=0;j<sz;j++){
                if(i!=j&&belongs[i]!=belongs[j])
                    G[belongs[i]][belongs[j]]=1;
            }
        }
    }
    
    //floyd算法找到每两条线路之间的最短换乘次数
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(G[i][k]!=INF&&G[k][j]!=INF)
                   G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
            }
        }
    }

    //处理每次查询
    for(auto inq:inquiries){
        auto begin_lines = mp[inq.first];
        auto end_lines = mp[inq.second];
        // for(int i=0;i<begin_lines.size();i++){
        //     cout<<begin_lines[i]<<" ";
        // } 
        // puts("");
        //  for(int i=0;i<end_lines.size();i++){
        //     cout<<end_lines[i]<<" ";
        // } 
        // puts("");
        int ret = INF;       
        for(int i=0;i<begin_lines.size();i++){
            for(int j=0;j<end_lines.size();j++){
                ret = min(ret,G[begin_lines[i]][end_lines[j]]);
            }
        }
        cout<<ret<<endl;
    }

}
int main(){
    least_change();
}

要注意，环线必须要进行处理

 if(j==m-1&&(lines[i][m-1]==lines[i][0]))
                continue;                  
  mp[lines[i][j]].push_back(i);

如果是环线的话，就别重复加它属于第i条线了，因为：

 //不同线路之间，是否能换乘，要手动判断
    for(auto station:mp){
        auto belongs = station.second;
        int sz = belongs.size();
        for(int i=0;i<sz;i++){
            for(int j=0;j<sz;j++){
                if(i!=j&&belongs[i]!=belongs[j])
                    G[belongs[i]][belongs[j]]=1;
            }
        }
    }

i ! = j的时候，belongs【i】有可能等于belongs【j】,如果两条线相同的话，换乘代价应该是0，而不是1，因此不需要重复加

Email loss

这题看着唬人，其实就是个求最短路径，没啥难的

题目描述

在这里插入图片描述

输入输出

在这里插入图片描述

样例

在这里插入图片描述

tip

注意这里n和m是一个量级的，因此是稀疏图，要用堆优化版的dijikstra算法，如果m和n^2 是一个量级的，那可以用朴素版。
无向图和有向图没区别，无向图就是A-B，B-A就行了。
其次，dijikstra算法中不能顺便把不能达到的点算了，因为根本就遍历不到它，只能找到s源点可以到达，但是时间超过t的。因此，需要在全部点的最短距离计算结束之后，再统一找不符合的点.
如果输出类型是固定的，那么printf要比cout的输出效率更高
endl还有刷新缓存区的功能，因此多次循环输出如果都用endl的话可能会超时，用"\n"换行效率更高

步骤

先用堆优化dijistra计算所有点到s源点的距离，注意，堆中存储的数据pair<元素1，元素2>,元素1必须是距离，元素2才是编号。因为堆排序的时候默认按照first排序。每次弹出当前回合距离s源点最近的。

代码段

全局变量设定

都是一些套路了

typedef long long ll;
const ll INF = 2e18;
using namespace std;
const int N =1e6+10;
typedef pair<ll,ll> PII;
ll e[N],ne[N],w[N],h[N],idx;
ll n,m,s,t;//点，边，源点，最大时间
ll dist[N];
bool st[N];

完整代码

void solve(){
    cin>>n>>m>>s>>t;
    memset(h,-1,sizeof h);
    fill(dist,dist+N,INF);
    dist[s]=0;
    for(ll i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});
    
    //堆优化
    while(q.size()){
        auto top = q.top();
        q.pop();
        
        ll val = top.second,distance = top.first;
        if(st[val])continue;
        st[val]=true;
        
        for(int i=h[val];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>distance+w[i]){
                dist[j]=distance+w[i];
                q.push({dist[j],j});
            }
        }
    }

    vector<PII> vec;
    for(int i=1;i<=n;i++){
        if(dist[i]==INF){
            vec.push_back({i,-1});
        }else if(dist[i]>t){
            vec.push_back({i,dist[i]});
        }
    }
    cout<<vec.size()<<"\n";
    for(auto v :vec){
        cout<<v.first<<" "<<v.second<<endl;
    }
}
int main(){
    solve();
    return 0;
}

莫卡的最远点对

题目描述

在这里插入图片描述

输入输出

在这里插入图片描述

样例

在这里插入图片描述这个题还需要补充一些树型DP还有树的直径的相关知识，等我学了再来写这个题吧

原文地址：https://blog.csdn.net/zxy13149285776/article/details/143719105

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：TSMC12nm工艺数字IC后端实现难点都有哪些？
下一篇：基于Java Springboot滁州市特产销售系统

自动化测试基础知识总结
自动化测试是软件测试活动中一个重要分支和组成部分，随着软件行业发展，市场对软件周期及软件质量要求越来越高，催生出来各种开发模式，比如常见开发模式敏捷开发，同时对我们测试人员提更高的要求，此时，产生自动
阅读更多2024-11-22
buuoj WEB做题笔记
buuctf靶场web类做题笔记
阅读更多2024-11-22
Python蓄水池算法详解与应用案例
蓄水池算法（Reservoir Sampling）是一种用于处理大规模数据流的随机抽样算法。该算法能够在不知道数据流大小的情况下，从数据流中均匀随机地抽取固定大小的样本。每个元素被选中的概率相等，保证
阅读更多2024-11-22
自然语言处理:第六十二章 KAG 超越GraphRAG的图谱框架
一个对大型语言模型（LLMs）友好的知识表示框架。SPG属性被划分为知识和信息领域，也称为静态和动态领域，它们分别与具有强模式约束的决策专长和具有开放信息表示的文档检索索引知识兼容。归功于在构建更有效
阅读更多2024-11-22
闲聊？泳池清洁机器人？
本章就来聊聊泳池清洁机器人行业。"博主本身就身在这个行业~~"，这个行业的前景还是不错的(为什么这么说？)。据统计，目前全球有3692万个泳池，每年呈持续增长态势。预计到2026年
阅读更多2024-11-22
vue学习11.21
v-model:value,也可以写为v-model，默认收集value值。如果写成data:()=>,就变成全局windows的对象了，原型上有的东西，模板上可以直接用，可以直接{{ }}输出
阅读更多2024-11-22
Python数据分析NumPy和pandas（四十、Python 中的建模库statsmodels 和 scikit-learn）
作为建模过程的一部分，可以在一个数据集上拟合模型，然后基于另一个数据集(可能是之前数据集的一部分作为测试集，也可能是后面操作后得到的数据集)评估模型。非数值数据可以通过多种不同的方式转换为模型设计矩阵
阅读更多2024-11-22
深入探索JMeter bin目录中的Properties文件：优化性能测试的关键
是JMeter中的一种机制，用于存储和管理配置信息和参数设置。Properties文件是一种键值对的集合，可以在整个测试计划中共享和使用。它们通常以“.properties”为扩展名，并使用简单的文本
阅读更多2024-11-22
Jmeter中的断言（二）
假设我们需要测试一个Web应用，并验证两个请求的响应数据是否相同。假设我们有一个简单的测试计划，包含一个线程组和一个HTTP请求，并希望验证登录请求的 HTML 响应数据中。假设我们有一个简单的测试计
阅读更多2024-11-22
【实战】使用YOLO11进行驾驶疲劳检测及警报【附源码与详细说明】
【实战】使用YOLO11进行驾驶疲劳检测及警报【附源码与详细说明】
阅读更多2024-11-22

北航软件算法C4--图部分

C4上级图部分

TOPO!

步骤

代码段

TOPO排序部分

完整代码

简单的图图

题目描述

输入输出

样例

步骤

代码段

开辟vector容器作为dist二维数组

初始化

调用Floyd算法

查询

完整代码

负环

题目描述

输入输出

样例

步骤

代码段

全局变量定义

spfa1函数用于判断是否有负环

spfa2用于记录每个点到1号点的距离

完整代码

直击西溜线（地铁最短换乘次数）

题目描述

输入输出

样例

步骤

tip

代码段

全局变量设定

完整代码

Email loss

题目描述

输入输出

样例

tip

步骤

代码段

全局变量设定

完整代码

莫卡的最远点对

题目描述

输入输出

样例

相关文章