当前位置：首页 > article >正文

蓝桥杯每日真题 - 第13天

article 2024/11/16 10:13:54

题目：（删边问题）

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