当前位置: 首页 > news >正文

题解:P13017 [GESP202506 七级] 线图

首先明白定义: 线图 L(G)L(G)L(G) 的顶点对应原图 GGG 的边,当且仅当原图中的两条边有公共顶点时,对应的线图顶点之间有一条边。

不难想到,对于原图中的每个顶点 vvv,其度数 d(v)d(v)d(v) 对应的边集可以形成 (d(v)2)\binom{d(v)}{2}(2d(v)) 对相邻边。每对相邻边在线图中会产生一条边。

用公式表示就是这样的(设 G=(V,E)G = (V,E)G=(V,E)):

∣EL(G)∣=∑v∈V(d(v)2)=∑v∈Vd(v)×(d(v)−1)2|E_{L(G)}| = \sum\limits_{v \in V} \binom{d(v)}{2} = \sum\limits_{v \in V} \frac{d(v) \times (d(v) - 1)}{2}EL(G)=vV(2d(v))=vV2d(v)×(d(v)1)

Code:

#include <bits/stdc++.h>
#define int long long  // 开long long!
using namespace std;
signed main() {int n, m;cin >> n >> m;vector<int> d(n + 1, 0);// 统计每个顶点的度数for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;d[u]++, d[v]++;}// 计算所有顶点的度数组合数之和int ans = 0;for (int i = 1; i <= n; ++i) {ans += d[i] * (d[i] - 1) / 2;}cout << ans << endl;return 0;
}
http://www.lryc.cn/news/583506.html

相关文章:

  • RAC-CELL(小区)处理
  • 射频前端的革新力量:ATR2057超低噪声放大器深度解析
  • C#基础篇(10)集合类之列表
  • AMIS全栈低代码开发
  • Claude Code 开发使用技巧
  • 一天一道Sql题(day05)
  • 双立柱式带锯床cad【1张总图】+设计说明书+绛重
  • MS32C001-C单片机,32位ARM M0+内核,宽电压、低功耗、小封装。
  • Python PyDub详解:音频处理从未如此简单
  • 高效集成-C#全能打印报表设计器诞生记
  • Paimon 原子提交实现
  • 无人机雷达模块运行与技术解析
  • 【RK3568+PG2L50H开发板实验例程】FPGA部分 | ROM、RAM、FIFO 的使用
  • UI前端与数字孪生结合实践探索:智慧物流的仓储优化与管理系统
  • 缓存三大问题详解与工业级解决方案
  • 分类预测 | Matlab基于KPCA-ISSA-SVM和ISSA-SVM和SSA-SVM和SVM多模型分类预测对比
  • 【算法训练营Day10】栈与队列part2
  • 微算法科技从量子比特到多级系统,Qudits技术革新引领量子计算新时代
  • 三码合一:OneCode注解驱动的新时代编码范式
  • C++学习笔记三
  • 类模板的语法
  • Python标准库:时间与随机数全解析
  • 【面试精讲】I2C 子系统核心结构与常见问题深度解析
  • MySQL 09 普通索引和唯一索引
  • 汽车功能安全-软件单元验证 (Software Unit Verification)【用例导出方法、输出物】8
  • 装配式建筑4.0:当房子像汽车一样被“智造”
  • 解锁DevOps潜力:如何选择合适的CI/CD工作流工具
  • 北京-4年功能测试2年空窗-报培训班学测开-第四十六天
  • Spring AI Alibaba Graph使用案例多节点并行执行
  • Webpack、Vite配置技巧与CI/CD流程搭建全解析