视频加载失败

图论1

920 字
5 分钟
图论1

题目描述#

星图有 n 个顶点,编号从 1 到 n,初始没有边。你需要添加恰好 m 条无向边,使星图满足以下条件:

  • 不存在自环或重边,即每条边连接两个不同顶点,任意两个顶点之间至多有一条边;
  • 恰好有 k 个连通块。

请你构造一张符合要求的星图,使得存在路径相连的顶点对 (u, v) (1 <= u < v <= n) 的数量尽可能多。若无法构造,请输出 -1。

【名词解释】 连通块:也称连通分量,满足,

  • 是原图的一个子图;
  • 连通块内的任意两个顶点之间都存在路径相连,且路径上的点也在连通块内;
  • 是极大的,即不能再通过添加原图中的其他顶点而依旧保持连通性; 单独的点也构成一个连通块。连通块的大小即为连通块中顶点的数量。

输入描述#

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 <= T <= 1000) 代表数据组数,每组测试数据描述如下:

第一行输入三个整数 n, m, k (1 <= k <= n <= 1000; 1 <= m <= 10^6),表示顶点数、需要添加的边数、要求的连通块数。

除此之外,保证单个测试文件的 n 之和不超过 1000。

输出描述#

对于每组测试数据,新起一行。

若无解,请输出 -1;否则,请参考下方格式输出:

  • 输出 m 行,第 i 行输出两个整数 u_i, v_i (1 <= u_i, v_i <= n; u_i != v_i),表示第 i 条无向边连接顶点 u_i, v_i。

如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。

示例1#

输入

4
1 1 1
5 3 2
11 451 4
4 6 1

输出

-1
1 3
1 5
4 3
-1
1 2
1 3
1 4
2 3
2 4
3 4

图的构造:连通块与路径相连点对#

题意#

有 n 个点,要求添加恰好 m 条不同的无向边,使图恰好有 k 个连通块,并让路径相连的点对数量尽可能多。无解输出 -1。

核心观察#

如果一个连通块有 s 个点,那么其中任意两点都路径相连,贡献:

C(s, 2) = s * (s - 1) / 2

为了让总点对数最大,应让一个连通块尽可能大,其余连通块都只包含一个点。

因此最优的连通块大小是:

n - k + 1, 1, 1, ..., 1

可行性判断#

  • 保证 k 个连通块,至少需要 n - k 条边;
  • 最大连通块有 n-k+1 个点,最多可以放 C(n-k+1, 2) 条边。

所以必须满足:

n - k <= m <= C(n-k+1, 2)

否则输出 -1。

构造方法#

令:

L = n - k + 1
  1. 让 1~L 构成最大的连通块;
  2. 让 L+1~n 都单独存在,形成 k-1 个单点连通块;
  3. 先添加星形边:(1,2), (1,3), ..., (1,L),共 L-1=n-k 条,保证大连通块连通;
  4. 按任意顺序继续添加 1~L 内还没有添加过的边,直到总数达到 m。

由于所有额外边都在大连通块内部,所以不会改变连通块数量,也能达到最优点对数。

我的代码#

#include <bits/stdc++.h>
using namespace std;
int main ()
{
int t;
cin>>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;
int p=(n-k+1)*(n-k)/2;
if(n==1)
{
cout<<"-1"<<endl;
continue;
}
if(m<n-k||m>p)
{
cout<<"-1"<<endl;
continue;
}
int op=0;
for(int i=1;i<n-k+1;i++)
{
if(op==m)
{
break;
}
for(int l=i+1;l<=n-k+1;l++)
{
cout<<i<<" "<<l<<endl;
op++;
if(op==m)
{
break;
}
}
}
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

图论1
https://www.xiaobaibai454.top/posts/study-26-11-14/
作者
Xiao_baibai
发布于
2026-11-14
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录