蓝桥杯备赛 Day 21 图论基础

图的基础

![[图的基础.png]]

1.图的存储方式

(1)邻接表(常用)

vector<pair<int,int>> g[N]; //g[x]存放x的所有出点信息,二维数组
g[i][j]={first,second},first是从i出发的第j个出点,second表示边权
例如上图:
g[1]={{2,0}.{3,0}}
g[6]={{3,7}}
g[4]={{5,0},{6,0}}
for(auto &y:g[x])

(2)邻接矩阵

d[i][j]表示i到j的边的距离，不存在为inf(无穷)
例如上图:
d[1][2]=0
g[6][3]=7
g[4][3]=inf
所以对于每个i，都要枚举所有j(1-n)，判断是不是无穷

遍历图

DFS

//使用bistset<N>比bool数组更好
bitset<N> vis;//vis[i]=true说明i已经走过
void dfs(int x){vis[x]=true;for(const auot &y:g[x]){if(vis[y]) continue;dfs(y);}
}

BFS

bitset<N> vis;//vis[i]=true说明i已经走过
queue<int> q;//q表示待拓展的点队列
q.emplace(1);
while(q.size()){//只要队列不为空int x=q.front();q.pop();if(vis[x]) continue;vis[x]=true;//放入同一层的结点for(const auto& y:g[x]) q.emplace(y);
}

3891帮派弟位

学习:
1.此题利用树就能写，DFS更新子树数组sz,然后自定义排序cmp即可
2.因为无需换根，所有邻接表只要存储题目表示的父子关系即可
g[v].emplace_back(u);
代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
vector<int> g[N]; //邻接表
int sz[N]; //子树
int n,m; void dfs(int x,int f){sz[x]=1;//遍历儿子for(const auto &y:g[x]){if(y==f)	continue;dfs(y,x);sz[x]+=sz[y];} 
}//自定义排序
bool cmp(int &x,int &y){//先按子树大小if(sz[x]!=sz[y])	return sz[x]>sz[y];//再按序号return x<y; 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;//g[u].emplace_back(v); //无需存储g[v].emplace_back(u);}dfs(1,0);//排序vector<int> ans;for(int i=1;i<=n;i++)	ans.emplace_back(i);sort(ans.begin(),ans.end(),cmp); for(int i=0;i<n;i++){if(ans[i]==m){cout<<i+1;break;}}return 0;
}

3352可行路径的方案数

学习:
1.此题为图例中的最短路径问题，不适合深度搜索DFS，而应该用层序搜索BFS，使用队列实现
2.开一个最短距离数组dist,最短距离的路径数量数组cnt
3.不要vis数组，因为一个点会访问多次
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=2e5+10,mod=1e9+7; 
vector<int> g[N]; //邻接表
ll dist[N]; //1到i的最短距离数组 
ll cnt[N]; //1到i的最短距离的路径和数组
int n,m;void bfs(){//创建队列queue<int> q;//从1开始q.emplace(1);dist[1]=0;cnt[1]=1;//开始bfs while(!q.empty()){int x=q.front();q.pop();//遍历for(const auto &y:g[x]){//未访问过,肯定最小，因为是bfsif(dist[y]==-1){//y从x访问过来 dist[y]=dist[x]+1;//y的路径数和x的路径数一样 cnt[y]=cnt[x];//放入y q.emplace(y);} //访问过，且等于最短的else if(dist[y]==dist[x]+1){//y的路径数再加上x的路径数cnt[y]=(cnt[y]+cnt[x])%mod; } 	 } } 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;g[a].emplace_back(b);g[b].emplace_back(a);}//初始化d,cntmemset(dist,-1,sizeof(dist));memset(cnt,0,sizeof(cnt)); bfs();cout<<cnt[n];return 0;
}

拓扑排序

![[拓扑排序.png]]

学习

1.针对“有向无环图”，是一种枚举点的顺序算法，要求当处理某个点时，其所有的入点都已经处理过了（例如上面要处理2，保证4和6都已经处理过了）
2.拓扑排序要求起始点是入度为0的点，如上图的1或7
3.拓扑排序的顺序不固定，有多种可能性
4.利用入度数组ind和队列(queue)实现
代码:

//计算入度数组
while(m--){int u,v;cin>>u>>v;//u->vg[u].emplace_back(v);//更新indind[v]++;
}

//拓扑排序
void topo(){//队列queue<int> q;//入度为0的点先入队列for(int i=1;i<=n;i++){if(!ind[i]){q.emplace(i);}}//处理队列元素while(!q.empty()){int x=q.front();q.pop();//遍历儿子for(const auto &y:g[x]){//x->y,y入度减1ind[y]--;//y入度为0,说明y的入度点全处理过了，y才能放入队列if(!ind[y]) q.emplace(y);}}
}
/*
输入:
7 8
1 4
1 6
4 2
6 2
2 3
6 3
7 3
2 5队列顺序:1 7 4 6 2 3 5
*/

拓扑排序+动态规划

1.当从x->y时，有状态转移dp[x]->dp[y]
代码:

//拓扑排序
void topo(){//队列queue<int> q;//入度为0的点先入队列for(int i=1;i<=n;i++){if(!ind[i]){q.emplace(i);}}//处理队列元素while(!q.empty()){int x=q.front();q.pop();//遍历儿子for(const auto &y:g[x]){//x->y,y入度减1ind[y]--;//动态规划,dp[x]->dp[y]dp[y]=f(dp[x])//y入度为0,说明y的入度点全处理过了，y才能放入队列if(!ind[y]) q.emplace(y);}}
}

1337走多远

学习:
1.经典拓扑排序加动态规划，dp数组表示入度为0的点到当前点的最大距离，因为一个y可能有多个x到达，所以有状态转移方程dp[y]=max(dp[y],dp[x]+1)，最终答案ans就等于dp数组中的最大值
代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,m,ind[N]; //ind[i]为第i个点的入度
ll dp[N],ans;//dp[i]为入度为0的点到第i个点的最大距离
vector<int> g[N]; void topo(){queue<int> q;//入度为0的点入队列for(int i=1;i<=n;i++){if(!ind[i]){q.emplace(i);}} //遍历队列while(!q.empty()){int x=q.front();q.pop();//遍历儿子for(const auto &y:g[x]){//ind[y]--ind[y]--;//更新dp[y]dp[y]=max(dp[y],dp[x]+1);//y入度为0则入队列if(!ind[y])	q.emplace(y); } } 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;while(m--){int u,v;cin>>u>>v;g[u].emplace_back(v);ind[v]++;}bool flag=false;//入度为0的点都不存在儿子则输出0for(int i=1;i<=n;i++){if(ind[i]==0 && g[i].size()!=0){flag=true;}} if(!flag){cout<<0;return 0;}topo();//获得答案for(int i=1;i<=n;i++){if(dp[i]>ans)	ans=dp[i];} cout<<ans;return 0;
}

3351最小字典序排列

学习:
1.此题要求即拓扑排序的要求，但是难点在于拓扑排序的结果有很多种可能，答案要最小字典序排序，已知拓扑排序能实现在队列中的元素肯定是入度为0了，只要保证每次取出来的最小即可，将队列更换为优先级队列，每次取出来的元素放入ans数组，最终根据ans数组答案输出结果即可
代码:

#include <bits/stdc++.h>using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,m,ind[N]; //ind[i]为第i个点的入度
vector<int> g[N];
vector<int> ans; void topo(){//优先级队列，保证出的元素是当前队列中最小的priority_queue<int,vector<int>,greater<int>> q;//入度为0的点入队列for(int i=1;i<=n;i++){if(!ind[i]){q.emplace(i);}} //遍历队列while(!q.empty()){int x=q.top();q.pop();ans.emplace_back(x);//遍历儿子for(const auto &y:g[x]){//ind[y]--ind[y]--;//y入度为0则入队列if(!ind[y])	q.emplace(y); } } 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;while(m--){int u,v;cin>>u>>v;g[u].emplace_back(v);ind[v]++;}topo();if(ans.size()<n)	cout<<-1;else{for(const auto &x:ans)	cout<<x<<" ";}return 0;
}

最短路径问题

1.Floyd算法:多源最短路问题,无负权,n<=500,稠密图,O(n^3),无向图
2.Dijkstra算法::单源最短路问题,*无负权,稀疏图,O(nlogm),堆优化,有向图(邻接表就存一个)

Floyd算法

学习:
1.本质是动态规划，用来解决多源最短路问题，即可以求得任意dp[i][j](从i到j)的距离
2.通过枚举中间点k，实现状态转移
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]
3.枚举顺序:中间点必须最先枚举，否则先枚举i和j，再枚举k，如果i到j的最短路要经过多个中间点，会发生错误，而先枚举中间点，是一小段一小段更新的
4.要求边权不能为负数
5.算法复杂的O(n^3),所以只能解决n<=500的问题(优先判断)
6.注意dp的初始化:

const ll inf=1e18
//尽量不用memset处理除了0和-1以外的其他值
for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=inf;}
} 
//每个点到自己距离为0
for(int i=1;i<=n;i++)	dp[i][i]=0;
//放止多重边 
dp[u][v]=min(dp[u][v],w);
dp[v][u]=min(dp[v][u],w);

代码:

//先枚举中间点k
for(int k=1;k<=n;k++){//再枚举i和jfor(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//状态转移dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}
}

1121蓝桥公园

学习:
1.最大值inf开const ll inf=1e18(int最大开到1e9，long long最大开到1e18)
2.除了0和-1，其他赋值不要用memset,全遍历赋值

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=inf;}
} 

3.每个点到自己距离初始化为0

for(int i=1;i<=n;i++)	dp[i][i]=0;

4.放置输入多重边

dp[u][v]=min(dp[u][v],w);
dp[v][u]=min(dp[v][u],w);

代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int,ll> PIII;
const int N=410;
const ll Inf=1e18;
ll dp[N][N]; //最短路径
int n,m,q;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>q;//尽量不用memset处理除了0和-1以外的其他值for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=Inf;}} //每个点到自己距离为0for(int i=1;i<=n;i++)	dp[i][i]=0;for(int i=1;i<=m;i++){int u,v;ll w;cin>>u>>v>>w;//放止多重边 dp[u][v]=min(dp[u][v],w);dp[v][u]=min(dp[v][u],w);}	//floyd更新dpfor(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}} while(q--){int st,ed;cin>>st>>ed;if(dp[st][ed]==Inf)	cout<<-1<<endl;else	cout<<dp[st][ed]<<endl;}return 0;
}

Dijkstra算法

![[dijkstra算法.png]]
学习：
1.高效处理非负权边的单源最短路问题
2.按照Dijkstra算法的贪心思想，第一次走到的时候距离一定是最短距离，所以一个点不可能走第二次
2.堆优化版本，使用优先队列priority_queue实现
3.预备代码
代码:

ll d[N]; //i到源点的距离,初始化为Inf
bitset<N> vis;//表示某个点是否走过,按照Dijkstra算法的贪心思想，第一次走到的时候距离一定是最短距离，所以一个点不可能走第二次
struct Node{//x为点编号，w表示源点到x的最短距离int x;ll w; //初始化Node(int tx,ll tw):x(tx),w(tw){}//重载<号bool operator< (const Node &u)const{//先按w降序,优先队列中w最小的作为堆顶if(w!=u.w) return w>u.w; //u.w>w也行//再按x升序，优先队列中x大的作为堆顶(这个排序无所谓)return x>u.x;}
};priority_queue<Node> pq;

4.Dijkstra算法代码
代码:

//输入源点
void dijk(int st){d[st]=0;pq.emplace(st,d[st]);//遍历队列while(!pq.empty()){Node t=pq.top();pq.pop();//每个结点只遍历一次if(vis[t.x]) continue;//标记为走过vis[t.x]=true;//遍历儿子for(const auto &y:g[t.x]){//关键一步,x->y.first,若从x加上y.second到y.first小于原来的d[y.first],则更新if(d[t.x]+y.second<d[y.first]){//更新d[y.first]d[y.first]=d[t.x]+y.second;//放入队列pq.emplace(y.first,d[y.first]);}}}
}

1122蓝桥王国

学习:
1.还是要注意int和ll之间的转换
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
const int N=3e5+10;
const ll Inf=2e18;
int n,m;
vector<PII> g[N]; //邻接表存图
ll dist[N]; //st到i的最短距离 
struct Node{//x为结点编号，w为x到st的最短距离 int x;ll w;Node(int tx,ll tw):x(tx),w(tw){}bool operator< (const Node &u)const{//w降序排，优先队列先取最短的距离 if(w!=u.w)	return w>u.w;//x降序排，优先队列先取最小的 return x>u.x;}
};
//优先队列
priority_queue<Node> pq;
bitset<N> vis;//dijstra算法
void dijkstra(int st){dist[st]=0;pq.emplace(st,dist[st]);//遍历优先队列while(!pq.empty()){Node t=pq.top();pq.pop();//遍历过来跳过if(vis[t.x])	continue;//更新vis vis[t.x]=true;//遍历儿子for(const auto &y:g[t.x]){//x经过y.second距离到达y.first，比之间的最短距离短，则更新if(dist[t.x]+y.second<dist[y.first]){dist[y.first]=dist[t.x]+y.second;//放入y,拓展 pq.emplace(y.first,dist[y.first]); } } } 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;//初始化距离for(int i=1;i<=n;i++)	dist[i]=Inf;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u].emplace_back(v,w);}dijkstra(1);for(int i=1;i<=n;i++){if(dist[i]==Inf)	cout<<-1<<" ";else cout<<dist[i]<<" ";}return 0;
}

Johnson算法(待看)

学习:
1.三步走:
(1)设置超级源点，用BellmanFord求单源最短路得到"势能"
(2)在势能的帮助下重新设置每条边的权重
(3)跑n次Dijkstra算法计算出所有点的单源最短路，即得到了全源最短路

生成树

1.最小生成树(MST)(无向图):
对于一个连通图，剔除其中一部分边，而保留一部分边，使得剩下的部分构成一颗树，此时共n个顶点，n-1条边，并且这棵树的所有边的权值之和最小(能够连接所有结点)
2.两种算法求解
Kruskal(O(mlogm))(遍历边)
Prim(O(mlogn))
3.最小生成树性质
(1)边权和是所有生成树中最小的
(2)最大边权是所有生成树中最小的
![[prim和kruskal区别.png]]

Kruskal(常用，一般都是稀疏图)

学习:
1.贪心思想，连接u和v权值最小的边
2.步骤
(1)将所有边按照边权升序排序(结构体数组＋重新operator<)
(2)从小到大遍历边(u,v),如果(u,v)已经连通则跳过(压缩路径并查集判断)，否则就连通(u,v)(并查集合并)
代码:

//结构体边
struct Edge{//顶点u,v,边权wint u,v;ll w;//初始化Edge(int tu,int tv,ll tw):u(tu),v(tv),w(tw){}//重新operator<bool operator<(const Edge &e)const{//按边权升序，数组前面元素是边权小的return w>e.w;}
};
//边数组
vector<Edge> es;
//父亲结点数组
int pre[N];
//路径压缩找根
int root(int x){//是根if(pre[x]==x) return x;pre[x]=root(pre[x]);return pre[x];
}
//kruskal算法
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) pre[i]=i;for(int i=1;i<=m;i++){int u,v,w;es.emplace_bakc(u,v,w);//不要更新pre[u]=v!!!,因为现在是存储边，下面遍历才连通u和v}//按边权排序sort(es.begin(),es.end());//按边权从小到大遍历(u,v)for(const auto &e:es){//已经连通则跳过(贪心保证之前的最小)if(root(e.u)==root(e.v)) continue;//没连通则连通,操作根结点pre[root(e.u)]=root(e.v);//更新答案ans=max(ans,e.w);}cout<<ans<<endl;
}

3322旅行销售员

学习:
1.因为推销员可以在城市加油，而在道路不能加油，所有答案ans油箱的最小容量就是最小生成树的最大一个边权值,ans=max(ans,e.c)
2.不要忘记struct里面初始化Edge(int tu,int tv,ll tw):u(tu),v(tv),w(tw){}
3.不要再输入存储边的时候更新pre,是在下面遍历边的时候才合并结点更新pre
代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
typedef long long ll;
int pre[N]; //记录父亲
//边
struct Edge{int u,v;ll w;//初始化Edge(int tu,int tv,ll tw):u(tu),v(tv),w(tw){} //按边权升序bool operator<(const Edge &e)const{return w<e.w;} 
}; 
int t;
//找根
int root(int x){if(pre[x]==x)	return x;pre[x]=root(pre[x]);return pre[x];
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>t;while(t--){int n,m;ll ans=0;cin>>n>>m;//边数组vector<Edge> es;//初始化prefor(int i=1;i<=n;i++)	pre[i]=i;for(int i=1;i<=m;i++){int x,y;ll c;cin>>x>>y>>c;//x->yes.emplace_back(x,y,c);} //排序sort(es.begin(),es.end());//按边权从小到大遍历(u,v)for(const auto &e:es){//u，v已经连通if(root(e.u)==root(e.v))	continue;//未连通则合并 pre[root(e.u)]=root(e.v);//更新ansans=max(ans,e.w); } cout<<ans<<endl;}return 0;
}

Prim算法

学习:
1.维护一个mst集合，里面储存已经在最小生成树中的点
2.dist数组表示dist[x]:x到mst集合中所有点的最短距离
3.步骤:
(1)从起点(1)开始，每次找出不在mst集合中，dist最小的点x,将他放入mst中
(2)因为将x放入mst中，所以要更新非mst集合的点的dist(因为他们到x的距离可能小于他们到原不含x的mst集合中的点的距离)
dist[y]=min(dist[y],w)(w为x->y的距离)
(3)如果dist[y]变小，则放入优先队列中
4.实现
mst集合用bitset来实现，等价于dijkstra里面的vis数组，判断一个点有没有访问过
5.与dijkstra算法区别:
(1)dist数组的含义

dijkstra:dist[i]表示源点到i的最短距离
Prim:dist[i]表示i到mst集合中的点的最短距离

(2)
dijkstra算法处理有向图，邻接表只存一个
而prim算法解决最小生成树，为无向图，邻接表要存两个
代码:

struct Edge{int x;//x为边的终点ll w;//w为x到集合的最短距离Edge(int tx,ll tw):x(tx),w(tw){}//因为用优先队列存储，每次拿出来最小的w，所以w降序排列bool operator<(const Edge &e)const{if(w!=e.w) return w>e.w;//按结点编号降序return x>e.x;}
};
vector<Edge> g[N];//邻接表,g[i]存储了从i出发的所有边
//都要存储
//g[u].emplace_back(v,w);
//g[v].emplace_back(u,w);//dist
ll dist[N];
int n,m;void prim(){//优先队列priority_queue<Edge> pq;//mst集合bitset<N> vis;//从1开始//在mst里面的元素到mst距离为0dist[1]=0;pq.emplace(1,dist[1]);ll ans=0;//最小生成树的最大边权//遍历队列while(!pq.empty()){Edge e=pq.top();pq.pop();if(vis[e.x]) continue;//将e.x放入mst集合vis[e.x]=true;res=max(res,dist[e.x]);//遍历儿子for(const auto &e2:g[e.x]){if(vis[e2.x]) continue;//更新此时不在mst集合里面的dist[e2.x]dist[e2.x]=min(dist[e2.x],e2.w);pq.emplace(e2.x,dist[e2.x]);}}
}

3322旅行销售员

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll Inf=1e18;
int t;
//边
struct Edge{int x; //边终点x ll w;//初始化Edge(int tx,ll tw):x(tx),w(tw){} //按边权降序，优先队列 bool operator<(const Edge &e)const{if(w!=e.w)  return w>e.w;return x>e.x;} 
}; 
ll dist[N];
vector<Edge> g[N];ll prim(){ll ans=0;priority_queue<Edge> pq;bitset<N> vis;//从1开始dist[1]=0;pq.emplace(1,dist[1]);while(!pq.empty()){Edge e=pq.top();pq.pop();if(vis[e.x])	continue;//e.x进入集合 vis[e.x]=true;ans=max(e.w,ans);for(const auto &e2:g[e.x]){if(vis[e2.x])	continue;//e.x->e2.x//更新dist[e2.x]dist[e2.x]=min(dist[e2.x],e2.w);pq.emplace(e2.x,dist[e2.x]); }} return ans;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>t;while(t--){int n,m;cin>>n>>m;//dist初始化 for(int i=1;i<=n;i++)	dist[i]=Inf;//g清空for(int i=1;i<=n;i++){g[i].clear();}for(int i=1;i<=m;i++){int x,y;ll c;cin>>x>>y>>c;//无向图 g[x].emplace_back(y,c);g[y].emplace_back(x,c);} cout<<prim()<<endl;}return 0;
}