Codeforces Round 954 (Div. 3) F. Non-academic Problem

在这里插入图片描述
思路:考虑缩点,因为是无向图,所以双连通分量缩完点后是一棵树,我们去枚举删除每一条树边的答案,然后取最小值即可。

#include <bits/stdc++.h>using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<int,int> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,m;
vector<pll> e[N];
vector<int> e2[N];
vector<vector<int> > vdcc;
int dfsn[N],low[N],tot,b[N],sz[N];
stack<int> s;void add(int u,int v,int i)
{e[u].push_back({v,i});e[v].push_back({u,i});
}void tarjan(int x,int f)//tarjan 求边双连通分量
{dfsn[x]=low[x]=++tot,s.push(x);for(auto [u,i]: e[x]){if(!dfsn[u]){tarjan(u,i);low[x]=min(low[x],low[u]);}else if(f!=i) low[x]=min(low[x],dfsn[u]);}if(dfsn[x]==low[x]){vector<int> c;while(1){auto t=s.top();b[t]=vdcc.size();sz[vdcc.size()]++;c.push_back(t);s.pop();if(t==x) break;}vdcc.push_back(c);}
}void init()
{tot=0;for(int i=0;i<=n;i++){e[i].clear();e2[i].clear();dfsn[i]=b[i]=sz[i]=low[i]=0;}vdcc.clear();}ll ans=1e18;int dfs(int x,int f)
{ll sum=0;for(auto u: e2[x]){if(u!=f) sum+=dfs(u,x);}sum+=sz[x];ll res=n-sum;ans=min(ans,(sum)*(sum-1)/2+(res-1)*res/2);return sum;
}void solve()
{cin>>n>>m;init();ans=1e18;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v,i);}for(int i=1;i<=n;i++){if(!dfsn[i]) tarjan(i,-1);}for(int i=1;i<=n;i++){for(auto [j,id]: e[i]){if(b[i]!=b[j]){e2[b[i]].push_back(b[j]);// e2[b[j]].push_back(b[i]);}}}dfs(b[1],-1);cout<<ans<<endl;
} int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/372933.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3-6 构建线性模型解决温度计示数转换问题

3-6 构建线性模型解决温度计示数转换问题 直接上源码 %matplotlib inline import numpy as np import torch torch.set_printoptions(edgeitems2, linewidth75)导入必要的库并设置 PyTorch 的打印选项&#xff0c;确保在打印张量时显示边缘项和行宽。 #%% t_c [0.5, 14.0,…

gpt-4o看图说话-根据图片回答问题

问题&#xff1a;中国的人口老龄化究竟有多严重&#xff1f; 代码下实现如下&#xff1a;&#xff08;直接调用openai的chat接口&#xff09; import os import base64 import requests def encode_image(image_path): """ 对图片文件进行 Base64 编码 输入…

phpexcel导入导出

前言&#xff1a; 如果你到处的excel软件打开有问题&#xff0c;下面有介绍解决办法 导入 1. composer init 初始化 2. 下载phpspreadsheet 这里需要注意php版本&#xff0c;需要大于7.2 composer require phpoffice/phpspreadsheet3. 编写代码 <?php require vendo…

Linux多进程和多线程(八)多线程

多线程 线程定义线程与进程线程资源 线程相关命令 pidstat 命令 top 命令ps 命令常见的并发方案 1. 多进程模式2. 多线程模式 创建线程 1. pthread_create() 示例:创建一个线程 2. pthread_exit() 退出线程3. pthread_join() 等待线程结束 示例: 线程分离 创建多个线程 示例 1:…

“郑商企航”暑期社会实践赴美丽美艳直播基地开展调研

马常旭文化传媒网讯&#xff08;记者张明辉报道&#xff09;导读&#xff1a;2024 年 7 月 3 日&#xff0c;商学院暑期社会实践团“郑商企航”在河南省郑州市新密市岳村镇美丽美艳直播基地&#xff0c;展开了一场意义非凡的考察活动&#xff0c;团队成员深度调研了直播基地的产…

CTF php RCE(二)

0x04 php伪协议 这种我们是先看到了include才会想到&#xff0c;利用伪协议来外带文件内容&#xff0c;但是有些同学会问&#xff0c;我们怎么知道文件名是哪个&#xff0c;哪个文件名才是正确的&#xff0c;那么这里我们就得靠猜了 include函数 因为 include 是一个特殊的语…

C++笔试强训3

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、选择题1-5题6-10题 二、编程题题目一题目二 一、选择题 1-5题 如图所示&#xff0c;如图所示p-3指向的元素是6&#xff0c;printf里面的是%s&#xff0c;从6开…

Python入门 2024/7/8

目录 数据容器 dict(字典&#xff0c;映射) 语法 定义字典字面量 定义字典变量 定义空字典 从字典中基于key获取value 字典的嵌套 字典的常用操作 新增元素 更新元素 删除元素 清空字典 获取全部的key 遍历字典 统计字典内的元素数量 练习 数据容器的通用操作…

SQLite 命令行客户端 + Windows 批处理应用

SQLite 命令行客户端 Windows 批处理应用 下载 SQLite 客户端1. Bat 辅助脚本1. 执行SQL.bat执行 2. 导出Excel.bat执行效果 3. 导出HTML.bat执行效果 4. 清空-订单表.bat5. 订单表.bat 2. 测试 SQL1. 创建订单表.sql2. 插入订单表.sql3. 查询订单表.sql4. 清空订单表.sql5. 删…

Sentinel-1 Level 1数据处理的详细算法定义(二)

《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程&#xff0c;以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下&…

Vuforia AR篇(八)— AR塔防上篇

目录 前言一、设置Vuforia AR环境1. 添加AR Camera2. 设置目标图像 二、创建塔防游戏基础1. 导入素材2. 搭建场景3. 创建敌人4. 创建脚本 前言 在增强现实&#xff08;AR&#xff09;技术快速发展的今天&#xff0c;Vuforia作为一个强大的AR开发平台&#xff0c;为开发者提供了…

前端图表库G2快速上手

文档地址&#xff1a; https://g2-v3.antv.vision/zh/docs/manual/getting-started/ https://g2.antv.antgroup.com/ 安装&#xff1a; pnpm i antv/g2在vue3中使用&#xff1a; <script setup> import {Chart} from antv/g2; import {onMounted} from "vue"…

python_zabbix

zabbix官网地址&#xff1a;19. API19. APIhttps://www.zabbix.com/documentation/4.2/zh/manual/api 每个版本可以有些差异&#xff0c;选择目前的版本在查看对于的api接口#token接口代码 import requests apiurl "http://zabbix地址/api_jsonrpc.php" data {&quo…

五、保存数据到Excel、sqlite(爬虫及数据可视化)

五、保存数据到Excel、sqlite&#xff08;爬虫及数据可视化&#xff09; 1&#xff0c;保存数据到excel1.1 保存九九乘法表到excel&#xff08;1&#xff09;代码testXwlt.py&#xff08;2&#xff09;excel保存结果 1.2 爬取电影详情并保存到excel&#xff08;1&#xff09;代…

苍穹外卖--启用和禁用员工

实现 package com.sky.controller.admin;import com.sky.constant.JwtClaimsConstant; import com.sky.dto.EmployeeDTO; import com.sky.dto.EmployeeLoginDTO; import com.sky.dto.EmployeePageQueryDTO; import com.sky.entity.Employee; import com.sky.properties.JwtPro…

使用Python绘制直方图并分析数据

使用Python绘制直方图并分析数据 在这篇博客中&#xff0c;我们将探讨如何使用Python中的pandas库和matplotlib库来绘制直方图&#xff0c;并分析数据文件中的内容。直方图是一种常用的图表类型&#xff0c;用于展示数据的分布情况。 代码示例 以下是一个完整的代码示例&a…

【2】A-Frame核心设计

一、基于HTML和Primitives的表达 1.HTML - 超文本标记语言 A-Frame 基于 HTML 和 DOM 之上&#xff0c;使用自定义元素的 polyfill。 HTML 是 Web 的构建块&#xff0c;提供了最易于访问的计算语言之一。无需安装或构建步骤&#xff0c;使用 HTML 创建仅涉及 HTML 文件中的文…

无人机之穿越机注意事项篇

一、检查设备 每次飞行前都要仔细检查穿越机的每个部件&#xff0c;确保所有功能正常&#xff0c;特别是电池和电机。 二、遵守法律 了解并遵循你所在地区关于无人机的飞行规定&#xff0c;避免非法飞行。 三、评估环境 在飞行前检查周围环境&#xff0c;确保没有障碍物和…

182440-00SF 同轴连接器

型号简介 182440-00SF是Southwest Microwave的一款连接器。该连接器采用 BeCu UNqS C17300 材料&#xff0c;并进行了镀金处理&#xff0c;以确保良好的导电性和耐腐蚀性&#xff1b;螺纹采用符合 ASTM A2582 标准的钢制合金&#xff0c;并进行磷酸盐钝化处理&#xff0c;以提高…

Labview_压缩文件

调用顺序 源文件 生成后的文件 1.新建ZIP文件 生成ZIP文件的路径&#xff1a;为最终生成ZIP文件的路径&#xff0c;需要提供ZIP文件的名称和类型 2.添加文件到压缩文件 源文件路径&#xff1a;为需要压缩的文件路径&#xff0c;非文件夹路径 生成ZIP文件时的路径&#x…