神奇的贪心和计数。

Table of Contents

  1. Description
  2. Solution

Description

Zy大帝拥有$n$个星球，因为距离非常遥远，所以Zy在他所居住的1号星球和他的军事基地霸中所在的2号星球建造了两个传送门，这样从1号星球到2号星球就只需要250分钟，回去也一样（双向）。

由于科技的发展，各个星球陆陆续续建造了和自己居民最经常去的星球之间的传送门，并且他们的传送门只需要1个小时（真快啊！），他们发现和别的星球建设传送门对促进经济发展有很大的帮助，于是向和其他所有星球建设传送门发展，Zy突然发现两两星球的传送门的建设会威胁到他的安全，可是他又想促进自己帝国的发展，于是他请到了他精心培养的你，希望你能帮他解决这个难题。

Solution

这题的意思就是让1和2之间至少有5条边, 那么我们考虑将图分成六个独立的集合, 顺次有连接, 这样遍历六个集合就至少有五条边. 其中每个集合本身是一个完全子图, 然后每个集合和下一个集合中的点有两两连边.

首先我们证明第一个策略, 首尾集合分别只有1, 2两个点.

如果把和1同一集合的点移向下一个集合, 她和1的连边, 和下一个集合的连边不受影响, 同时她还可以向下一个的下一个连边, 这样答案更优. 尾集合同理.

然后证明第二个策略, 只有在给定图中和1, 2有边的点在第二个/倒数第二个集合中.

考虑一个初始和1无边的点, 如果她在第二个集合, 她只能和第三集合, 第二集合以及1连边, 而将她移至第三集合后, 可以和第三集合, 第二集合以及第四集合连边, 答案至少不会变劣. 另一侧的情况同理.

那么我们就得到了一些散点, 下面我们只需要考虑她们每个点更靠近哪一边, 因为这些点两两之间都已经有连边, 所以将她们靠向第二/倒数第二集合中较大的一个就可以了. 需要注意的是有一些点在给定图中就和第二/倒数第二集合有连边, 这些点的归属是固定的, 需要特判.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

const int maxn = 40005;
const int maxm = 1e+6 + 5;

struct edge
{
  int to, nxt;
}e[maxm << 1];
int n, m, ptr, lnk[maxn];
int id[maxn], sza, szb, szr, fre, toa, tob;

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  n = rd(); m = rd();
  int u, v;
  for (int i = 1; i <= m; ++i) {
    u = rd(); v = rd();
    add(u, v); 
    add(v, u);
  }
  for (int p = lnk[1]; p; p = e[p].nxt) {
    int y = e[p].to;
    id[y] = 1; sza++;
  }
  for (int p = lnk[2]; p; p = e[p].nxt) {
    int y = e[p].to;
    id[y] = 2; szb++;
  }
  int res = n - sza - szb - 2;
  int ans = sza * (sza - 1) / 2 + szb * (szb - 1) / 2 + 
            res * (res - 1) / 2 + sza + szb;
  for (int i = 3; i <= n; ++i) 
    if (!id[i]) {
      for (int p = lnk[i]; p; p = e[p].nxt) {
        int y = e[p].to;
        if (id[y] == 1) toa++;
        else if (id[y] == 2) tob++;
        if(id[y]) break;
      }
  }
  fre = res - toa - tob;
  ans += toa * sza + tob * szb + fre * max(sza, szb);
  ans = ans - m;
  printf("%d\n", ans);
  return 0;
}