题解：P11762 [IAMOI R1] 走亲访友
Deltary_
·
·
题解
题意
给出一张 n 个点，m 条边的无向连通图，图中无自环、重边，初始位置为 s，每次沿边移动，移动后可以选择是否删除当前这条边。未删除的边可以多次移动，求构造 k 步移动内未删除边组成树的移动方案。
对于 100 \% 的数据，n \leq 10^3，n - 1 \leq m \leq \frac{n(n - 1)}{2}，k \leq m + n。保证有解。
Subtask 1、2 和 4
考虑先钦定一棵生成树，在树上移动并且删除剩下不在生成树上的边。容易发现遍历整棵树时，树上每条边最多经过 2 次，而对于每条多余的边，一去一回删除也最多经过 2 次，总移动步数最多为 2m 次，又有 m \leq \frac{n(n - 1)}{2}，则移动步数严格小于 n^2，可通过 Subtask 1、2 和 4。
Subtask 3
其实用上面所述生成树的写法也可以。
## Subtask 5
前面的 Subtask 其实和正解没有特别强的相关性。注意到如果这张图是一张欧拉图，那么肯定有一个显然的解法：还是钦定一棵生成树，在跑欧拉路径的时候判断若为树边则保留，否则删去。这样的最大移动步数为 $m$ 次。
于是考虑怎么把一张普通的图变成一张欧拉图。往图中加边，在 dfs 遍历生成树上节点的时候，判断该点度数是否为偶。若为奇则向父节点连边。可以证明最后会形成一个欧拉图。
对于增加的边，由于原先向父节点的连边为树边，所以保证这条边不会被删除。根节点不用向上连边，最多增加边数为 $n - 1$，总移动次数严格小于 $n + m$。
实现细节上要注意在 dfs 遍历的同时不要加边。这是未定义行为。可能会导致 RE 或 WA。
::::info[如何证明“最后一定会形成一个欧拉图”？]
简单意会即可。欧拉图的总度数必为偶数，保证了根节点以下的度数均为偶，那么根节点的度数也必然为偶。
::::
::::success[代码]
dfs 的时候可以直接生成树，我也不知道当时为什么写了个并查集。
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
#define FILENAME "path"
const int N = 3e6 + 10;
const i64 P = 1e9 + 7;
struct node {
int v, tag, ID;
node() : v(0), tag(0), ID(0) {}
node(int v, int tag, int ID) : v(v), tag(tag), ID(ID) {}
};
int n, m, k, s;
int deg[N], fa[N], etag[N]; // etag：每条边对应的 tag
vector <node> G[N];
int rel[N], vis[N]; // rel：新建边对应的旧边编号
int Find(int x) {
return (x == fa[x]) ? x : fa[x] = Find(fa[x]);
}
// 构造欧拉图
vector <node> V[N];
void dfs1(int u, int f, int fid) {
for(auto [v, tag, ID] : G[u]) {
if(v == f) continue;
if(tag == 1) dfs1(v, u, ID);
}
if((deg[u] & 1) && u != s) {
m++;
G[u].emplace_back(node(f, 2, m));
V[f].emplace_back(node(u, 2, m)); // 不要在遍历时加边
rel[m] = fid, etag[m] = 2, deg[u]++, deg[f]++;
}
return void();
}
// 无向图欧拉路径
vector <pii> ans;
int now[N];
void dfs2(int u, int fid) {
if(vis[fid]) return void();
vis[fid] = 1;
for(; now[u] < G[u].size();) {
auto [v, tag, ID] = G[u][now[u]++];
dfs2(v, ID);
}
if(fid) ans.emplace_back(make_pair(fid, etag[fid]));
return void();
}
void solve() {
cin >> n >> m >> k >> s;
int rm = m;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
int uu = Find(u), vv = Find(v);
if(uu == vv) {
etag[i] = 0;
G[u].emplace_back(node(v, 0, i)); G[v].emplace_back(node(u, 0, i));
} else {
etag[i] = 1;
G[u].emplace_back(node(v, 1, i)); G[v].emplace_back(node(u, 1, i));
fa[uu] = vv;
}
deg[u]++, deg[v]++;
}
dfs1(s, s, 0);
for(int i = 1; i <= n; i++) {
for(auto k : V[i]) G[i].push_back(k);
}
dfs2(s, 0);
reverse(ans.begin(), ans.end());
cout << ans.size() << '\n';
for(auto [i, j] : ans) cout << (i > rm ? rel[i] : i) << ' ' << (j ? 1 : 0) << '\n';
return void();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef FILENAME
freopen(FILENAME ".in", "r", stdin);
freopen(FILENAME ".out", "w", stdout);
#endif
solve();
return 0;
}
```
::::