JZOJ 6838. 【2020.10.31提高組模擬】小j的組合
題目大意
- 給出一棵初始大小為 n n n的樹，可以如下操作：
- 選擇一個選擇一個點 v v v，再新增一個點 v ′ v' v′，將 v ′ v' v′連向所有與 v v v相連的點，
- 求最少的操作次數及方案使得圖中存在一條哈密頓回路，
- n ≤ 100 n\leq 100 n≤100
題解
- 哈密頓回路需要把每個點都經過一遍且只能經過一遍，除非是一條鏈，否則在樹上都是不存在的，
- 可以發現操作相當于把每個點復制一遍， 等同于給允許這個點多經過一次，有了這個結論就容易了許多，
- 在樹上DFS，每次回傳到父親就需要操作一次，但這樣不能保證操作最少（當然，最后不需要回到根節點）
- 不需要回傳的點構成了一條鏈，剩下的每個點都需要回傳操作一次，那么顯然當這條鏈最長也就是直徑的時候，操作次數最少，
- 直接找出直徑模擬即可，
代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 110
int dis[N][N], p[N];
int ans[N * 2], sum, n;
void dfs(int k, int t) {
int x = 0;
ans[++ans[0]] = k, p[k] = 1;
for(int i = 1; i <= n; i++) if(dis[k][i] == 1 && !p[i]) {
if(dis[t][i] + 1 == dis[t][k]) {
x = i;
continue;
}
dfs(i, t);
printf("%d ", k);
ans[++ans[0]] = ++sum;
}
if(x) dfs(x, t);
}
int main() {
int i, j, k, x, y;
scanf("%d", &n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) if(i == j) dis[i][j] = 0; else dis[i][j] = N;
for(i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
dis[x][y] = dis[y][x] = 1;
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) dis[i][j] = min(dis[i][k] + dis[j][k], dis[i][j]);
int s = 1, t = 1;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) if(dis[i][j] > dis[s][t]) s = i, t = j;
printf("%d\n", n - dis[s][t] - 1);
sum = n;
dfs(s, t);
printf("\n");
for(i = 1; i <= ans[0]; i++) printf("%d ", ans[i]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200118.html
標籤：python
上一篇：gmoj 6838. 【2020.10.31提高組模擬】小j的組合
下一篇：概率dp習題