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

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;}//对角线初始化为0for(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;}}
}

负环

题目描述

输入输出

样例

步骤

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

代码段

全局变量定义

#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();}}
}

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

题目描述

输入输出

样例

步骤

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

tip

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

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

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

这么输入。

3. 访问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图初始化为INFfill(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);}}//同一线路上的站点，换乘代价为0for(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还有树的直径的相关知识，等我学了再来写这个题吧