• 【算法每日一练]-图论（保姆级教程 篇5（LCA，最短路，分层图）） #LCA #最短路计数 #社交网络 #飞行路线 # 第二短路

    今天讲最短路统计和分层图

    目录

    题目：LCA 

    思路：

    题目：最短路计数

    思路：

    题目：社交网络

    思路：

    题目：飞行路线 

    思路：

    题目：第二短路

    思路：

            

            

    题目：LCA 

            

    思路：

            

    非常明显了，之前就说过倍增迭代就是一个一个选区间使总长度达到 M（凑一个数），用不大于它最大的二的次幂，减去之后，再重复这个过程。所以LCA+倍增逼近是最快的。

                    

    1. #include //最近公共祖先LCA P3379：给一棵数，求任意两点的LCA 
    2. using namespace std;
    3. const int maxn=500002;
    4. int n,m,s,tot=0;
    5. int head[maxn],d[maxn],p[maxn][21];//d存的是深度（deep）,p[i][j]存的从i向上走2的j次方那么长的路径到的父节点
    6. struct node{int v,next;}e[maxn*2];//存数要开两倍
    7. void add(int u,int v){e[++tot]={v,head[u]};head[u]=tot;}     
    8.          
    9. void dfs(int u,int fa)// 首先进行的预处理，将所有点的deep和p的初始值dfs出来
    10. {
    11.     d[u]=d[fa]+1; p[u][0]=fa;  //处理深度,父节点
    12.     for(int i=1;(1<//i
    13.         p[u][i]=p[p[u][i-1]][i-1];
    14.     for(int i=head[u];i;i=e[i].next){ //处理u的孩子的st表
    15.         int v=e[i].v;
    16.         if(v!=fa) dfs(v,u);//只能向下走，不能向上走
    17.     }
    18. }                              
    19. int lca(int a,int b) //非常标准的lca查找（两次逼近）
    20. {
    21.     if(d[a]>d[b]) swap(a,b);   //保证a是在b结点上方（d[b]大）
    22.     for(int i=20;i>=0;i--){
    23.     	if(d[a]<=d[b]-(1<//向上逼近（b向上移到和a同一个深度）
    24. 	}  
    25.     if(a==b) return a;  //特判
    26.     for(int i=20;i>=0;i--)
    27.     {
    28.         if(p[a][i]==p[b][i]) continue; //向上逼近（A和B一起向上，不断逼近最下端的公共祖先）
    29.         else a=p[a][i],b=p[b][i];     
    30.     }
    31.     return p[a][0];  //找出最后a值的数字
    32. }
    33. int main()
    34. {
    35.     int a,b;
    36.     scanf("%d%d%d",&n,&m,&s);//n个结点，m次询问，s是树根编号
    37.     for(int i=1;i
    38.         scanf("%d%d",&a,&b);
    39.         add(a,b); add(b,a); //无向图，要加两次              
    40.     }
    41.     dfs(s,0);
    42.     for(int i=1;i<=m;i++)
    43.     {
    44.         scanf("%d%d",&a,&b);
    45.         printf("%d\n",lca(a,b));
    46.     }
    47.     return 0;
    48. }

            

             

    题目：最短路计数

                      

    思路：

            

    注意到每条路径的权值都是1，难怪结果会那么大。

            

    dikjkstra和spfa版本最短路计数：
    1，维护最短路时产生的：那就是映射关系（因为引入的是周围点，相当于ans[v]=ans[cur]*1）
    2，新最短路：发现了新的最短路就相加

            
    floyd版本最短路计数：
    1，维护最短路时产生的：（因为引入的是任意点，故ans[i][j]=ans[i][k]*ans[k][j]）
    2，新最短路：发现了新的最短路就相加

    、        

    1. #include 
    2. using namespace std;
    3. typedef pair<int,int> pii;
    4. const int N=1e6+5,M=2e6+5;
    5. int mod=100003,n,m,tot=0;
    6. int head[N],vis[N],dis[N],ans[N];
    7. priority_queue,greater>Q;
    8. struct node {int to;int next;}e[M*2];
    9. void add(int u,int v){e[++tot]=(node){v,head[u]};head[u]=tot;}
    10. void dijkstra(int s){
    11. 	memset(dis,0x3f,sizeof(dis));
    12. 	Q.push({0,s});dis[s]=0;ans[s]=1;
    13. 	while(!Q.empty()){
    14. 		int cur=Q.top().second;Q.pop();
    15. 		if(vis[cur])continue;//跳不跳无所谓，无非耗点时间
    16. 		vis[cur]=1;
    17. 		for(int i=head[cur];i;i=e[i].next)
    18. 		{
    19. 			int v=e[i].to;
    20. 			if(dis[cur]+11,ans[v]=ans[cur],Q.push({dis[v],v});//映射最短路(路过此点可以变短，那么最短路就和它有关)
    21. 			else if(dis[cur]+1==dis[v])ans[v]+=ans[cur],ans[v]%=mod;//新最短路(发现了另外的最短路就相加)
    22. 		}
    23. 	}
    24. }
    25. int main(){
    26. 	cin>>n>>m;int x,y;
    27. 	for(int i=1;i<=m;i++){
    28. 		scanf("%d%d",&x,&y);
    29. 		add(x,y);add(y,x);
    30. 	}
    31. 	dijkstra(1);
    32. 	//spfa(1);
    33. 	for(int i=1;i<=n;i++){
    34. 		cout<'\n';
    35. 	}
    36. }

                     

    1. //spfa版本：这个版本更快！！！！
    2. void spfa(int s){
    3. 	memset(dis,0x3f,sizeof(dis));
    4. 	queue<int>q;vis[s]=1;
    5. 	q.push(s);dis[s]=0;ans[s]=1;
    6. 	while(!q.empty()){
    7. 		int cur=q.front();q.pop();
    8. 		vis[cur]=0;
    9. 		for(int i=head[cur];i;i=e[i].next){
    10. 			int v=e[i].to;
    11. 			if(dis[cur]+1
    12. 			   dis[v]=dis[cur]+1;
    13. 			   ans[v]=ans[cur];
    14. 			   if(!vis[v])q.push(v),vis[v]=1;	
    15. 			}
    16. 			else if(dis[cur]+1==dis[v])ans[v]+=ans[cur],ans[v]%=mod;
    17. 		}
    18. 	}
    19. }

            

            

    题目：社交网络

                    

    思路：

            

    点i的重要程度=∑从s到t的且经过i最短路条数/从s到t的最短路条数（s!=i，t!=i）

    主要还是floyd算法，求出每个(i,j)对每个k的重要程度为ans[k]
    求到某点时最短路径数：
    1，只要最短路更新，那么最短路个数也要更新
    2，如果发现了新的最短路，那么就相加
            

    1. #include 
    2. using namespace std;   
    3. typedef long long ll;
    4. const int N=110;
    5. ll INF,dis[N][N],e[N][N];//e[i][j]表示（i，j）的最短路径数
    6. double ans[N];//每个点的重要程度
    7. int main(){
    8. 	int n,m;ll x,y,z;
    9. 	cin>>n>>m;
    10. 	memset(dis,0x7f,sizeof(dis));
    11. 	INF=dis[1][1];//初始化INF无穷大
    12. 	for(int i=1;i<=m;i++){
    13. 		scanf("%lld%lld%lld",&x,&y,&z);
    14. 		dis[x][y]=dis[y][x]=z;
    15. 		e[x][y]=e[y][x]=1;//初始化e[i][j]
    16. 	}
    17. 	for(int i=1;i<=n;i++)  dis[i][i]=0;//对角线为0，但是不写也对其余任何边都没有影响，写不写随你
    18. 	for(int k=1;k<=n;k++)
    19. 		for(int i=1;i<=n;i++)
    20. 		for(int j=1;j<=n;j++){
    21. 			if(dis[i][k]==INF||dis[k][j]==INF)continue;//有不通的就直接跳过
    22. 			if(dis[i][j]>dis[i][k]+dis[k][j]){
    23. 				dis[i][j]=dis[i][k]+dis[k][j];//每个边只会更新一次，即当前最优
    24. 				e[i][j]=e[i][k]*e[k][j];//只要最短路更新，则最短路对应的个数也要更新即可
    25. 				continue;
    26. 			}
    27. 			if(dis[i][j]==dis[i][k]+dis[k][j]){//找到了第二条最短路，就相加
    28. 				e[i][j]+=e[i][k]*e[k][j];
    29. 			}
    30. 		}
    31. 	for(int k=1;k<=n;k++)
    32. 		for(int i=1;i<=n;i++)
    33. 		for(int j=1;j<=n;j++){
    34. 			if(i==j||j==k||i==k)continue;
    35. 			if(dis[i][j]==dis[i][k]+dis[k][j])//对k遍历每个（i，j）
    36. 				ans[k]+=(1.0*e[i][k]*e[k][j])/e[i][j];
    37. 		}
    38. 	for(int i=1;i<=n;i++)
    39. 		printf("%0.3f\n",ans[i]);
    40. }

           

             

    题目：飞行路线 

            

                     

    思路：

            

     一个图中任意两个点都可以权值变成0，最多有k次，我们常常建立k层的分层图，相邻层所有点建立权值为0的立体边，然后跑最短路即可
            

    1. #include  
    2. using namespace std;
    3. int cnt,head[110005];
    4. int dis[110005];
    5. bool vis[110005]; //标记当前白点，如果不想用vis，也可以判断取出元素的dis和dis数组中值是否一样
    6. priority_queueint,int>,vectorint,int>>,greaterint,int>> > Q; //堆优化(first是值，second是下标)
    7. struct Edge{ int to,w,next;}e[2500001];
    8. void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,head[u]}; head[u]=cnt;}
    9. void Dijkstra(int s)//dijktra+堆优化
    10. {
    11.     memset(dis,0x3f,sizeof(dis));
    12.     dis[s]=0;
    13.     Q.push(make_pair(0,s));
    14.     while(!Q.empty())  //必须用empty， size是求大小的，会慢一些 !!!
    15.     {
    16. 		int u=Q.top().second; Q.pop();
    17. 		if(vis[u]) continue; //已经是白点的就跳过
    18. 	    vis[u]=1; //标记成白点
    19. 	    for(int i=head[u];i;i=e[i].next)
    20. 	    {
    21. 	        int v=e[i].to,w=e[i].w;
    22. 	        if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,Q.push(make_pair(dis[v],v));
    23. 	    }
    24.     }    
    25. }
    26.  
    27. int main()
    28. {
    29. 	int n,m,k,s,t;
    30. 	cin>>n>>m>>k>>s>>t; //城市数，航线数，免费次数，起始城市号，终点城市号
    31.     int u,v,c;
    32.     for(int i=0;i
    33.     {
    34.     	cin>>u>>v>>c;//两个城市航线，费用
    35.     	for(int j=0;j<=k;++j){//建立每层图
    36.     		add(u+j*n,v+j*n,c);
    37.             add(v+j*n,u+j*n,c);
    38.             if(j!=k){//第k层下面没有了，就别建了
    39.             	add(u+j*n,v+(j+1)*n,0); //分层图：所有相邻层间：上下层u，v的权值为0
    40.             	add(v+j*n,u+(j+1)*n,0);
    41. 			}
    42. 		}
    43.     }
    44.     for(int i=1;i<=k;++i)
    45. 	{
    46. 		add(t+(i-1)*n,t+i*n,0);
    47. 	}//处理奇葩数据
    48.     Dijkstra(s);
    49.     printf("%d",dis[t+k*n]);
    50.     return 0;
    51. }

             

             

    题目：第二短路

                     

    思路：

    1. #include
    2. using namespace std;   
    3. typedef pair<int,int> pii;
    4. const int N=5005,M=100005;
    5. int n,m,tot,flag;
    6. int head[N],d1[N],d2[N],vis[N];
    7. priority_queue,greater > Q;
    8. struct node{int to;int w;int next;}e[M*2];
    9. void add(int u,int v,int w){e[++tot]=(node){v,w,head[u]};head[u]=tot;}
    10. void dijkstra(int s){
    11. 	memset(d1,0x3f,sizeof(d1));//d1存放第一短路
    12. 	memset(d2,0x3f,sizeof(d2));//d2存放第二短路
    13. 	Q.push(make_pair(0,s));d1[s]=0;
    14. 	while(!Q.empty()){
    15. 		int cur=Q.top().second;Q.pop();
    16. 		if(vis[cur])continue;//vis数组可有可无，即便旧白点引入也掀不起变化，无非多走了几步
    17. 		vis[cur]=1;
    18. 		for(int i=head[cur];i;i=e[i].next){
    19. 			int v=e[i].to,w=e[i].w;flag=0;
    20. 			if(d1[cur]+w1;//维护最短路，更新前的最短路就是次短路
    21. 			if(d1[cur]+w>d1[v]&&d1[cur]+w1;//最短路没有变化，更新次短路
    22. 			if(d2[cur]+w1;//维护次短路,如果d2[s]初始化成0,那么这个地方就出问题了
    23. 			if(flag)Q.push(make_pair(d1[v],v));
    24. 		}
    25. 	}
    26. }
    27. int main(){
    28. 	cin>>n>>m;int u,v,w;
    29. 	for(int i=1;i<=m;i++){
    30. 		scanf("%d%d%d",&u,&v,&w);
    31. 		add(u,v,w);add(v,u,w);
    32. 	}
    33. 	dijkstra(1);
    34. 	cout<
    35. }

  • 相关阅读:
    Java查询数据放入word模板中并在前端导出下载
    Java 面试题 (二) -------- Java 集合相关
    swift基础学习笔记
    无人不识又无人不迷糊的this
    Spring Boot对接RocketMQ示例
    Apache DolphinScheduler 系统架构设计
    Android基础-进程间通信
    mybatis02
    十、MySql的索引（重点）
    计算机毕业设计 基于微信小程序的“共享书角”图书借还管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解
  • 原文地址：https://blog.csdn.net/m0_69478376/article/details/134360310