假装已经知道了要走哪些边,可以发现答案就确定了。那么问题就是确定走哪些边。首先输入的肯定要走,并且还要再加一些,使得可以形成欧拉路。
欧拉路不好处理,就从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;
}