P7729

发表于 本文字数： 2.9k 阅读时长 ≈ 3 分钟

给定 mm 个二元组 (ai,bi)(a_i,b_i)，构造一张 m−1m-1 条边的图，使得 ∑dis(ai,bi)\sum dis(a_i,b_i) 最小，并求方案数对 109+710^9+7 取模。

n≤2000,nm≤2×107n\le 2000,nm\le 2\times 10^7 。

直接给出最优解方案：先 ai,bia_i,b_i 连边得到一张图，在图上找到最小环，将最小环上的边断掉，重新一棵贡献最小的树最优。

毛看看挺对的，证明还是有点意思的。

设图的最小环为 cc，那么这样做的答案就是 m−2+cm-2+c。

新图上，有 mm 条路径，m−1m-1 条边，利用线代相关知识可以说明可以选出路径的一个非空子集满足只选这些路径，每条边经过偶数次。

假设选出来的最小子集对应的路径为 P1,P2,...,PkP_1,P_2,...,P_k。

此时可以看出 k≤ck\le c，因为只选最小环上这些路径是一条回路，满足条件。

然后高妙一步是，把这些路径的 (ai,bi)(a_i,b_i) 作为虚边加入，此时由于是若干个环，所以每个点度数是偶数，而去掉虚边后每个点度数依然是偶数，所以只保留虚边每个点度数为偶数，因此存在环，所以 k≥ck\ge c。

所以得到 k=ck=c

∑i=1m∣Pi∣≥2∣⋃i=1kPi∣+(m−k)≥2(k−1)+(m−k)=m−2+c\sum_{i=1}^m |P_i|\ge 2|\bigcup_{i=1}^k P_i|+(m-k)\ge 2(k-1)+(m-k)=m-2+c

第一步是因为其他贡献至少为 11，每条覆盖的边贡献至少为 22。

第二步是 kk 个异或为 00，基的大小为 k−1k-1，因此至少包含 k−1k-1 条边。

此时得到了最小值，以及得到最小值的条件为：

  • 只有一个最小环上的边拆掉，其他不变。

  • 大小为 cc 的环拆出的贡献需要是 2c−22c-2 。

第一问等价与直接求最小环，场上不会做qwq。

其实很简单，每个点为起点，跑出到一个点的最短路和次段路组合起来即可。

两条路必须不交，否则一定存在更小环，其实只需要满足走的第一条边不同即可，这样代码很好写。

然后考虑方案数咋算，先考虑，如果只有一个环怎么做。

容易发现造的树的充要条件：每个子树都是一个区间。

因此很好 dp，分环和链两种情况，然后每次搞一个根去分开即可。

现在唯一的问题是，可能算重，这很不好处理。

算重的情况是，一个方案只动了两个环交的部分，容易发现这个部分 ≤c/2\le c/2 。

因此高妙的处理方法是，先算出环的方案乘以环的个数，然后减去所有只动了 ≤c/2\le c/2 的链的方案，然后去暴力枚举这样一条链，把方案加回去即可。

统计环的个数啥的是简单的，只需要记录一下最短路条数即可，由于最小环有一些性质，所以代码好写很多。

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
64
65
66
67
68
69
70
71
struct node {
  int y, z, r;
};

int main() {
#ifndef ONLINE_JUDGE
  IO(1);
#endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int n, m, _;
  cin >> n >> m >> _;
  V<Vi> e(n + 5);
  for (int i = 1, x, y; i <= m; i++) cin >> x >> y, e[x].pb(y), e[y].pb(x);

  V<Vi> d1(n + 5, Vi(n + 5, Inf)), d2(d1), s(d1);
  For(i, 1, n) {
    queue<node> q;
    d1[i][i] = d2[i][i] = 0;
    Vi rt(n + 5);
    for (int y : e[i]) q.push({y, 1, y});
    for (; !q.empty(); q.pop()) {
      auto x = q.front();
      int ff = 0;
      if (d1[i][x.y] == Inf) {
        d1[i][x.y] = x.z, rt[x.y] = x.r, s[i][x.y] = 1, ff = 1;
      } else if (x.r != rt[x.y]) {
        if (d2[i][x.y] == Inf) d2[i][x.y] = x.z, ff = 1;
        if (x.z == d1[i][x.y]) s[i][x.y] += 1;
      }
      if (ff)
        for (int y : e[x.y]) q.push({y, x.z + 1, x.r});
    }
  }

  int mc = Inf;
  For(i, 1, n) For(j, i + 1, n) mc = min(mc, d1[i][j] + d2[i][j]);
  if (mc > n) return cout << "-1\n-1", 0;
  cout << m + mc - 2 << '\n';

  mint C = 0;
  if (mc & 1) {
    For(i, 1, n) For(x, 1, n) if (i != x) {
      for (int y : e[x])
        if (y != i && d1[i][x] == d1[i][y] && d1[i][x] == mc / 2)
          C += s[i][x] * s[i][y];
    }
    C /= 2;
  } else {
    For(i, 1, n) For(j, 1, n) if (i != j && d1[i][j] * 2 == mc) {
      C += s[i][j] * (s[i][j] - 1) / 2;
    }
  }
  C /= mc;

  V<mint> f(n + 5), g(n + 5);
  g[1] = f[0] = f[1] = 1;
  For(i, 2, n) {
    For(j, 0, i - 1) g[i] += f[j] * f[i - j - 1];
    For(j, 0, i) f[i] += f[j] * g[i - j];
  }

  mint ans = C * f[mc - 1];
  V<mint> res(n + 5);
  For(i, 1, n) res[i] = g[i] + (i >= 2 ? g[i - 2] : 0_m) - 2 * g[i - 1];
  For(i, 1, mc / 2) ans -= C * mc * res[i];

  For(i, 1, n) For(j, i + 1, n) if (d1[i][j] + d2[i][j] == mc) ans +=
      res[d1[i][j]] * s[i][j];
  cout << ans << '\n';
}