Codeforces Beta Round #22 (Div. 2 Only) C. System Administrator（构造割点）

题目大意

给了 n 个节点以及一个特殊的顶点 v(3<=n<=10⁵)，让你用 m(0<=m<=10⁵) 条边建一个无向图，使得这个图以 v 为它的一个割点

做法分析

无向图中，一个割点同时属于两个点双连通分量

我们可以这样做，假设割点的一边是连通的（不一定是双连通），里面点的个数设为 x(不包括割点 v)，割点的另一边也是连通的，里面点的个数肯定是 n-x-1(不包括割点)

那么，两边中，边的总数最多是 C²_x+1+C²_n-x=x²+(1-n)*x+(n²-n)/2

注意：这是一个凹函数，对称轴是 x=(n-1)/2，且 x 的取值范围是 [1, n-2] 中的整数，要使函数取最大值，x 不是等于 1 就是 n-2(又对称性，二者等值)

也就是说，v 的一边只有一个节点，另一边有 n-2 个节点的时候，得到的边数最大，为 2-n+(n²-n)/2

边数的下界为：n-1（形成一棵树）

当 m 不再这个上下界中时，肯定不能构造出来图，当边数在这个区间中时，直接枚举点构造就行了（因为边肯定足够，也不会多，构造出来的图一定是符合条件的）

参考代码

C. System Administrator

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 LL n, m;
 9 int v;
10 
11 void deal(int s, int t, int edge)
12 {
13     for(int k=1; edge; k++)
14         for(int i=s; i+k<=t && edge; i++)
15         {
16             printf("%d %d\n", i, i+k);
17             edge--;
18         }
19 }
20 
21 int main()
22 {
23     scanf("%I64d%I64d%d", &n, &m, &v);
24 
25     if(m>(2-n+(n*n-n)/2) || m<n-1)
26     {
27         printf("-1\n");
28         return 0;
29     }
30     if(v==1)
31     {
32         printf("%d %I64d\n", v, n);
33         deal(1, n-1, m-1);
34     }
35     else
36     {
37         printf("%d %d\n", 1, v);
38         deal(2, n, m-1);
39     }
40     return 0;
41 }

题目链接 & AC通道

Codeforces Beta Round #22 (Div. 2 Only) C. System Administrator