蓝桥杯每日真题 - 第13天

devtools/2024/11/15 16:06:46/

题目:(删边问题)

题目描述(14届 C&C++ B组F题)

 

解题思路:

  • 图的构建:使用邻接链表表示图,边的起点和终点分别存储在数组中,以支持高效的遍历。

  • Tarjan算法:利用Tarjan算法找到割边(即桥),判断割边是否会将图分为两个连通分量。

  • 求解最小权值差:对于每条割边,计算割除后的两个连通分量的权值之差。遍历所有割边,求出权值差的最小值。

  • 结果输出:若找不到合法的删除方案(即不存在割边),输出-1;否则,输出最小权值差。

代码实现(C语言):

//建议先去学最短路劲生成(dijskra堆优化)和最小树生成(kruskal)后再来学tarjan算法
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//邻接链表
long long weight[200009];//点权
long long sum=0;//边权和
int end=0;
int head[2*200009];//每一个u对应的边的序号
int v[2*200009];//边从u到v
int next[2*200009];//前一个u起头的边//tarjan
int dfn[200009];//节点u搜索的次序编号
int low[200009];//u或者u的子树能追寻的最早的栈中的节点序号
int index=0;//访问点的个数
int mark[200009];//记录该点是否被访问过
long long ans=9999999999;//最小差值int N,M;//N个节点,M个边long long min(long long a,long long b)
{if(a<b) return a;else return b;
}void add(int U,int V)
{//建立邻接链表end++;v[end]=V;next[end]=head[U];head[U]=end;
}void tarjan(int x,int ine)//追寻到点x,访问的路劲的对应边的编号
{dfn[x]=++index;low[x]=index;//遍历x能走的边for(int i=head[x];i;i=next[i]){int t=v[i];if(dfn[t]==0)//mark{//没被访问,向下进行访问,直到把x的强联通图访问完tarjan(t,i);//向下访问后,回溯的时候赋值//min判断交叉时每条路劲的值,从而得到最小值low[x]=min(low[t],low[x]);weight[x]+=weight[t];//联通路劲点权和if(low[t]>dfn[x])//t的分支最终没连上跟{//砍掉t的分支,t分支实现内循环,并找到最小差值ans=min(ans,llabs(sum-2*weight[t]));}}//给每一个联通到跟的点赋值else if(i!=ine-1&&i!=ine+1) low[x]=min(low[x],dfn[t]);}
}
int main(int argc, char *argv[])
{// 请在此输入您的代码scanf("%d%d",&N,&M);for(int i=1;i<=N;i++){scanf("%lld",&weight[i]);sum+=weight[i];}for(int i=1;i<=M;i++){int U,V;scanf("%d%d",&U,&V);add(U,V);add(V,U);}tarjan(1,0);if(weight[1]!=sum)//没有联通 printf("%lld",sum-2*weight[1]);else {if(ans!=9999999999) printf("%lld",ans);else printf("-1");}return 0;
}

代码分析: 

  • 图的构建:使用邻接链表结构存储图,以便高效遍历所有边。

  • Tarjan算法:通过DFS和low数组计算割边。Tarjan算法能够在一次DFS中找到所有割边,效率较高。

  • 最小差值计算:在找到的割边中,计算每条割边将图分成的两个连通分量的权值差,并更新最小差值。

  • 结果输出:若没有找到合法的割边,输出-1,否则输出最小差值。

得到运行结果:

难度分析

⭐️⭐️⭐️⭐️

总结

  • 算法适用于解决无向图中的割边问题,并且能高效计算分割后的连通分量权值差。

  • Tarjan算法在一次深度优先搜索中找出割边,提高了效率,是处理连通分量问题的有效工具。

  • 代码逻辑较为复杂,尤其是在low和dfn数组的更新上,需要对图的割边和强连通分量有较好理解


http://www.ppmy.cn/devtools/134204.html

相关文章

Spark 共享变量:广播变量与累加器解析

Spark 的介绍与搭建&#xff1a;从理论到实践_spark环境搭建-CSDN博客 Spark 的Standalone集群环境安装与测试-CSDN博客 PySpark 本地开发环境搭建与实践-CSDN博客 Spark 程序开发与提交&#xff1a;本地与集群模式全解析-CSDN博客 Spark on YARN&#xff1a;Spark集群模式…

力扣-Hot100-哈希【算法学习day.30】

前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&am…

浅谈React的虚拟DOM

React的虚拟DOM&#xff1a;揭秘高效渲染的秘密 在React中&#xff0c;虚拟DOM&#xff08;Virtual DOM&#xff09;是一个核心概念&#xff0c;它是React能够提供高效渲染和更新的关键。虚拟DOM是一个轻量级的JavaScript对象&#xff0c;表示真实的DOM树。通过使用虚拟DOM&am…

Python工程加密打包(基于pyinstaller 6.11.1和pyarmor 9.0.5)(202411)

近期编写的PyQt客户端需要交付了&#xff0c;在交付之前面临如下两个问题&#xff1a;第一是将程序打包成exe&#xff0c;第二是对程序进行加密&#xff0c;毕竟生成的pyc文件是能被反编译出来的&#xff0c;甚至连注释都在。 联想到同样是脚本语言的Javascript采用混淆技术进行…

Vue的基础使用

一、为什么要学习Vue 1.前端必备技能 2.岗位多&#xff0c;绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能&#xff08;Vue2Vue3&#xff09; 二、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 构建用户界面 的 渐进式 框架…

【JAVA基础】JVM是什么?

JVM是什么? 一、JVM的基本概念二、JVM的特点三、JVM的结构四、JVM的运行时数据区域五、JVM的垃圾回收机制六、JVM的应用场景七、JVM的性能调优 一、JVM的基本概念 JVM是一种规范&#xff0c;本身是一个虚拟计算机&#xff0c;直接和操作系统进行交互&#xff0c;与硬件不直接…

中国前首富胡志标受邀出席创客匠人“全球创始人IP领袖高峰论坛”

创客匠人正式官宣&#xff01;原爱多VCD创始人、中国前首富胡志标受邀出席创客匠人5000人“全球创始人IP领袖高峰论坛”&#xff0c;将与我们携手共赴这场商业巅峰盛宴。 由创客匠人打造的“全球创始人IP领袖高峰论坛”将在2024年12月26日-28日在厦门市国际博览会议中心如期举…

KEIL5软件介绍

一、Debug问题 &#xff08;1&#xff09;debug过程中&#xff0c;在watch窗口中看不到局部变量的值&#xff0c;显示not in scope&#xff0c;并且警告variable "变量" was set but never used。 原因&#xff1a;编译器把变量优化掉了。局部变量&#xff0c;如果…