图论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
输入
41 1 15 3 211 451 44 6 1输出
-11 31 54 3-11 21 31 42 32 43 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~L构成最大的连通块; - 让
L+1~n都单独存在,形成k-1个单点连通块; - 先添加星形边:
(1,2), (1,3), ..., (1,L),共L-1=n-k条,保证大连通块连通; - 按任意顺序继续添加
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; } } }
}}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




