Village (Minimum)
边长为1的树上,每一个节点移动到另外一个不同的节点,求最小的总移动距离和。
这是一个比较巧妙的greedy算法,有点难理解,但是写起来非常简单:
- DFS顺序遍历所有节点
- 对于没有发生过交换的非根节点,和父亲交换,总移动距离+2。
- 对于根,和任何一个儿子交换,距离+2.
这个正确的原因如下:
- 对于没有和根发生过交换的节点,这样操作的最后结果,就是或者停留在父亲处(移动了1),或者停留在兄弟处(移动了2)。 不存在比这个更近的移动方案了,去其它地方都更远。
- 因为每次交换要求有至少一个没有动过,这就保证了这两个节点都不会回到最初的位置。每次这样操作后,在原位的节点数 就减少1或者2. 所以最近最多N次操作(一次DFS),就完成了。
- 根的操作增加的是最小值2,所以也是最优的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n; // 1e5
vector<int> adj[100005];
int ans;
int moveto[100005];
void dfs(int s, int e) {
for (int u: adj[s]) {
if (u == e) continue;
dfs(u, s);
}
if (s != 0 && moveto[s] == s) { // non-root nodes that are not moved - swap with parent
moveto[s] = e;
moveto[e] = s;
ans += 2;
} else if (s == 0 && moveto[0] == 0) { // if root is not moved - swap with any child
moveto[0] = *adj[0].begin();
moveto[*adj[0].begin()] = 0;
ans += 2;
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n-1; i++) {
int u,v;
scanf("%d %d", &u, &v);
u--,v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 0; i < n; i++) moveto[i] = i;
dfs(0, -1);
printf("%d\n", ans);
for (int i = 0; i < n; i++) {
printf("%s%d", i ? " " : "", moveto[i]+1);
}
return 0;
}