C4上级图部分
- TOPO!
- 步骤
- 代码段
- TOPO排序部分
- 完整代码
- 简单的图图
- 题目描述
- 输入输出
- 样例
- 步骤
- 代码段
- 开辟vector容器作为dist二维数组
- 初始化
- 调用Floyd算法
- 查询
- 完整代码
- 负环
- 题目描述
- 输入输出
- 样例
- 步骤
- 代码段
- 全局变量定义
- spfa1函数用于判断是否有负环
- spfa2用于记录每个点到1号点的距离
- 完整代码
- 直击西溜线（地铁最短换乘次数）
- 题目描述
- 输入输出
- 样例
- 步骤
- tip
- 代码段
- 全局变量设定
- 完整代码
- Email loss
- 题目描述
- 输入输出
- 样例
- tip
- 步骤
- 代码段
- 全局变量设定
- 完整代码
- 莫卡的最远点对
- 题目描述
- 输入输出
- 样例
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还有树的直径的相关知识，等我学了再来写这个题吧
