[联考2020 B卷] 丁香之路 [欧拉回路]

丁香之路

假装已经知道了要走哪些边，可以发现答案就确定了。那么问题就是确定走哪些边。首先输入的肯定要走，并且还要再加一些，使得可以形成欧拉路。

欧拉路不好处理，就从T到S连一条边变成欧拉回路。欧拉回路需要满足两个条件：度数是偶数，联通。

从小往大扫，如果两个点的度数都是奇数，就让它们连一条边。之后图中剩下了若干联通块。考虑连接它们。可以发现一定向最近的点连边比较优秀，于是只有O(n)条有用的边。贪心的把联通块连起来。

然后就发现自己过不了... 去loj orz了一下AC代码，发现了问题：把两个奇数连起来这条边不一定有用。确实我们要走回来，但是不一定走这条边。

于是可以把连一条边改成把中间所有点串成一条链。这样是正确的，因为中间的点左右各加一条边，奇偶性不变。

#include <bits/stdc++.h>
using std::cerr;
using std::endl;

inline int rd() {
  int b = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}

const int N = 2600;

int n, m, s, t, sum, ins[N];
int deg[N];

struct Edge { int x, y; };
std::vector<Edge> E[N];

int fa[N], Fa[N];
int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline int solve() {
  deg[s] ^= 1, deg[t] ^= 1;
  ++ins[s], ++ins[t];
  for (int i = 1; i <= n; ++i) {
    fa[i] = Fa[i];
    E[i].clear();
  }
  int ret = sum;
  for (int i = 1, j = 0; i <= n; ++i) {
    if (!(deg[i] & 1)) continue;
    if (!j) j = i;
    else {
      for (int k = j; k < i; ++k) {
        int x = find(k), y = find(k + 1);
        fa[x] = y;
      }
      ret += i - j, j = 0;
    }
  }
  for (int i = 1, j = 2; i <= n; ++i) {
    if (!ins[i]) continue;
    if (j <= i) j = i + 1;
    while (j <= n && (!ins[j] || find(j) == find(i)))
      ++j;
    if (j <= n) E[j - i].push_back({ i, j });
    else break;
  }
  for (int i = 1; i <= n; ++i)
    for (auto e : E[i]) {
      int x = find(e.x), y = find(e.y);
      if (x != y) {
        fa[x] = y, ret += 2 * i;
      }
    }
  deg[s] ^= 1, deg[t] ^= 1;
  --ins[s], --ins[t];
  return ret;
}

int main() {
  n = rd(), m = rd(), s = rd();
  for (int i = 1; i <= n; ++i)
    fa[i] = i;
  for (int i = 1; i <= m; ++i) {
    int x = rd(), y = rd();
    sum += std::abs(x - y);
    deg[x] ^= 1, deg[y] ^= 1;
    ++ins[x], ++ins[y];
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
  }
  for (int i = 1; i <= n; ++i)
    Fa[i] = fa[i];
  for (t = 1; t <= n; ++t)
    printf("%d ", solve());
  putchar('\n');
  return 0;
}