贝壳找房 · 组合数学 · 算法编程题
贝壳找房 组合数学 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

牛牛当上了牛客国的国王，在牛客国一共有 n 个城市，这 n 个城市之间原有 m 条航路，但是由于城市航路规划，需要删除一些航路，使剩下的航路刚好能让这 n 个城市联通，并且剩下的航路总载客量最大。牛客国的计数方式比较特别，他们喜欢用组合数 C_a^b 来计数。所以两个城市之间航路的载客量也是用 C_a^b 表示的。作为国师你能告诉牛牛剩下的航路的总载客量是多少呢，由于数可能很大请对 10^9+7 取模后告诉牛牛。

输入输出

输入描述
第一行为两个整数 n 和 m ，表示城市数量和原有航路条数。
接下来有 m 行，每行有四个整数 u,v,a,b ，表示一条航路之间的两个城市编号和航路载客量 C_a^b 中的 a 和 b 。
1≤ n≤ 10^3,1≤ m ≤ n*(n-1)/2,1≤ b≤ a≤ 10^3
输出描述
输出为一行，输出剩下的航路的总载客量并对 10^9+7 取模，若剩下的航路不能让所有城市联通输出 -1 。

样例共 1 组

样例 1
输入
5 5
1 2 1 1
1 5 1 1
3 5 1 1
2 4 1 1
4 5 2 1
输出
5

算法解析依据一般

考点：组合数学

数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e3
  • 元素值域：b ≤ 1e3，a ≤ 1e3（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

  1. 判断是分类计数（相加）还是分步计数（相乘）。
  2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
  3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
  4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

  • 把排列和组合搞混。
  • 取模意义下直接做除法（应乘逆元）。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：5 5 / 1 2 1 1 / 1 5 1 1 / 3 5 1 1 / 2 4 1 1 / 4 5 2 1
  • 输出：5

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招开发类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解