【图论】求合法 K 的最大值：二分答案 + 模拟检查
题目描述
给定一个
n
个点
m
条边的简单无向图，需要将其补充为完全图。补充规则是：事先选定参数
K
，每次只能添加满足 “
u,v
间无边且度数之和 ≥
K
” 的边。若存在一种连边序列能补全为完全图，则
K
合法。求最大的合法
K
。
输入格式
第一行：两个整数
n,m
（点数、边数）
接下来
m
行：每行两个整数
u,v
（表示一条无向边）
输出格式
一行一个整数：最大合法
K
样例输入
plaintext
4 3
1 2
2 3
3 4
样例输出
plaintext
3
解题思路
核心观察
合法
K
的取值具有单调性：若
K=x
合法，则所有
≤x
的
K
都合法（因为更低的
K
更容易满足度数和条件）。因此，我们可以用二分答案高效找到最大合法
K
。
二分答案的范围
最小可能值：1（任意图都能通过逐步添加边补全，
K=1
一定合法）
最大可能值：
2n−2
（完全图中每个节点度数为
n−1
，任意两点度数和为
2n−2
，初始图的
K
不可能超过此值）
Check 函数：验证 K 是否合法
对于给定的
K
，需模拟边的添加过程，判断能否补全为完全图。核心逻辑如下：
收集非相邻边：记录所有初始时不存在的边，每条边的 “权重” 初始化为其两个端点的初始度数之和（因为权重代表当前端点度数和，决定能否添加这条边）。
循环添加边：
每次遍历所有未添加的边，若某条边的权重 ≥
K
，则标记为 “已添加”。
添加边后，两个端点的度数各增加 1，因此所有与这两个端点相关的未添加边的权重需加 1（因为这些边的端点度数和发生了变化）。
终止条件：
若所有非相邻边都已添加（补全为完全图），返回 true。
若一轮遍历后无任何边可添加，且仍有边未添加，返回 false。
代码解析
变量定义
cpp
include<bits/stdc++.h>
using namespace std;
int n,m;
int g[505][505]; // 邻接矩阵：g[u][v]=1表示存在边，0表示不存在
int p[505]; // p[u]：节点u的初始度数
int f[505][5005]; // f[u][j]：记录与节点u相关的第j条非相邻边在h数组中的索引
struct Edge{ // 存储非相邻边的信息
int u, v; // 边的两个端点
int weight; // 当前端点度数之和（权重）
bool added; // 是否已添加
} h[500005]; // 存储所有非相邻边（n=500时最多~12万条，50万足够）
Check 函数实现
cpp
bool check(int K) {
int cnt = 0; // 非相邻边的总数
// 初始化：清空f数组，收集所有非相邻边
for(int i=1; i<=n; i++) f[i][0] = 0; // f[i][0]记录节点i关联的非相邻边数量
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
if(g[i][j] == 0) { // 非相邻边
cnt++;
h[cnt].u = i;
h[cnt].v = j;
h[cnt].weight = p[i] + p[j]; // 初始权重=初始度数和
h[cnt].added = false;
// 记录节点i和j与这条边的关联
f[i][++f[i][0]] = cnt;
f[j][++f[j][0]] = cnt;
}
}
}
while(true) {int added_cnt = 0; // 本轮已添加的边数int total_added = 0; // 累计已添加的边数// 统计当前已添加的边数for(int i=1; i<=cnt; i++) {if(h[i].added) total_added++;}if(total_added == cnt) return true; // 所有边都添加完，K合法// 遍历所有非相邻边，尝试添加for(int i=cnt; i>=1; i--) { // 从后往前遍历，不影响结果（可优化为按权重排序）if(h[i].added) continue;if(h[i].weight >= K) {// 标记为已添加h[i].added = true;added_cnt++;int u = h[i].u;int v = h[i].v;// 更新与u相关的所有非相邻边的权重（u度数+1）for(int j=1; j<=f[u][0]; j++) {int edge_idx = f[u][j];h[edge_idx].weight++;}// 更新与v相关的所有非相邻边的权重（v度数+1）for(int j=1; j<=f[v][0]; j++) {int edge_idx = f[v][j];h[edge_idx].weight++;}}}if(added_cnt == 0) return false; // 本轮无任何边可添加，K不合法
}
}
主函数：二分答案求解
cpp
int main() {
// 输入处理
scanf("%d%d", &n, &m);
memset(g, 0, sizeof(g));
memset(p, 0, sizeof(p));
for(int i=1; i<=m; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u][v] = 1;
g[v][u] = 1;
p[u]++; // 节点u度数+1
p[v]++; // 节点v度数+1
}
// 二分答案：从最大可能值往下找（也可标准二分：l=1, r=2n-2）
for(int K = 2*n; K >= 1; K--) { // K最大可能为2n-2，这里取2n足够if(check(K)) {printf("%d\n", K);return 0;}
}
return 0;
}
样例验证
以样例输入为例：
初始图：4 个节点，边 (1-2, 2-3, 3-4)
初始度数：p [1]=1, p [2]=2, p [3]=2, p [4]=1
非相邻边：(1-3, 1-4, 2-4)，初始权重分别为 1+2=3、1+1=2、2+1=3
当
K=3
时：
第一轮遍历：
边 (1-3) 权重 = 3 ≥3，添加；更新 1 和 3 相关边的权重：
1 相关边：(1-4) 权重变为 2+1=3，(1-3) 已添加
3 相关边：(2-4) 权重变为 3+1=4，(1-3) 已添加
边 (2-4) 权重 = 3 ≥3，添加；更新 2 和 4 相关边的权重：
2 相关边：无其他未添加边
4 相关边：(1-4) 权重变为 3+1=4
边 (1-4) 权重 = 4 ≥3，添加
所有边都添加完毕，返回 true，故
K=3
合法。
时间复杂度分析
二分次数：
O(n)
（从
2n
遍历到 1，或标准二分
O(logn)
）
每次 Check：
收集非相邻边：
O(n
2
)
循环添加边：最多循环
O(n
2
)
次（每条边添加一次），每次遍历边
O(n
2
)
，更新权重
O(n)
（每个节点关联的边最多
O(n)
条）
总复杂度：
O(n
3
)
，对于
n=500
，
500
3
=125e6
，可通过所有测试用例。
优化方向
二分方式：将 “从大到小遍历” 改为标准二分（l=1, r=2n-2），减少二分次数至
O(logn)
。
边的排序：在 Check 中，按权重从大到小遍历边，可减少无效遍历（优先添加权重高的边，更快触发后续权重更新）。
数组优化：使用动态数组（如 vector）替代固定大小数组，减少内存浪费。
总结
本题的核心是利用二分答案缩小
K
的范围，结合模拟边的添加过程验证合法性。关键在于理解 “添加边后更新相关边权重” 的逻辑 —— 因为端点度数变化会直接影响后续边的添加条件。这种 “二分 + 模拟” 的思路在图论可行性问题中较为常见，可灵活应用于类似场景