补题 10.2模拟 T1 图的建立
编辑
13
2025-10-03
A. 图的建立
给定一个包含 n 个点、m 条边的简单无向图，
现在需要把这张图补充为一张完全图，但有一个特殊要求：
- 先选定一个参数 K；
- 随后反复进行连边操作：仅当顶点 u,v 间当前没有边，且它们的度数之和 至少为 K 时，才允许连边 (u,v)。
若存在一种连边顺序，使得在该参数 K 下最终图能变为完全图，则称 K 是合法的。
求所有合法的 K 的最大值。对于所有测试数据，1\le n\le 500, 1\le m< n(n - 1)/2, 1\le u, v\le n。
思路分析
简单观察不难发现只需每次连边贪心选择度之和最大且无边连通的两节点连接即可，记录连边过程中最小的度之和即为答案。即最终的合法 K，等于加边过程中遇到的最小的 \deg_u+\deg_v。但是直接遍历为 O(n^4) ，无法通过。
考虑优化，注意到度之和不超过 2n ，题目中 n\le500 ，可以使用 2n 个桶存放未连边的节点的度之和。之后每次从大小最大且非空的桶中取出一条边连接，更新桶中剩下的边。优化为 O(n^3) 。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int G[509][509];
int deg[509];
vector<pair<int,int> > b[1109];
int main(){
// freopen("graph.in","r",stdin);
// freopen("graph.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
deg[u]++,deg[v]++;
G[u][v]=1,G[v][u]=1;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(!G[i][j]) b[deg[i]+deg[j]].push_back({i,j});
}
int tot=m;
for(int k=2*n-2;k>=0;k--){
while(!b[k].empty()){
int u=b[k].back().first,v=b[k].back().second;
b[k].pop_back();
if(G[u][v]) continue;
G[u][v]=1,G[v][u]=1;
deg[u]++,deg[v]++,tot++;
for(int i=1;i<=n;i++){
if(i==u||i==v) continue; // 避免自环，这个点有点坑
if(!G[u][i]){
b[deg[u]+deg[i]].push_back({u,i});
}
if(!G[v][i]){
b[deg[v]+deg[i]].push_back({v,i});
}
}
}
if(tot==n*(n-1)/2){
cout<<k<<endl;
return 0;
}
}
return 0;
}
- 0
- 0
-
分享