蓝桥杯每日真题 - 第13天

2025/6/17 21:09:32 来源：https://blog.csdn.net/weixin_74066588/article/details/143758518 浏览: 次关键词：蓝桥杯每日真题 - 第13天

题目：（删边问题）

题目描述（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;
}