1092E Minimal Diameter Forest
解题报告
直接手玩猜贪心策略:把直径的中点(如果有两个,取任意一个)互相连接起来,而且一定是连成菊花图最优。
取哪个作为菊花图的中心点呢?继续手玩可以猜到,一定是直径最大的联通块的直径中点。
证明也很显然。
代码实现
const int MAXN = 1000 + 10;
int n, m;
std::vector<int> G[MAXN];
int cnt, bel[MAXN], maxdist[MAXN], mdnode[MAXN];
int diameter[MAXN];
int dep[MAXN][MAXN]; int fdist[MAXN];
std::vector<int> midlen;
void dfs0(int u, int fa, int b) {
bel[u] = b;
forall (G[u], i) {
int v = G[u][i];
if (v == fa) continue;
dfs0(v, u, b);
}
}
void dfs1(int u, int fa, int *dis) {
forall (G[u], i) {
int v = G[u][i];
if (v == fa) continue;
dis[v] = dis[u] + 1;
dfs1(v, u, dis);
}
}
std::vector<std::pair<int, int> > vs;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
G[u].push_back(v); G[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
if (!bel[i]) {
dfs0(i, 0, ++cnt);
} dfs1(i, 0, dep[i]);
} memset(maxdist, 0x3f, sizeof maxdist);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (bel[i] != bel[j]) continue;
diameter[bel[i]] = std::max(diameter[bel[i]], dep[i][j]);
}
}
for (int i = 1; i <= n; ++i) {
int mdis = 0;
int b = bel[i];
for (int j = 1; j <= n; ++j) {
if (i == j || bel[i] != bel[j]) continue;
mdis = std::max(mdis, dep[i][j]);
} if (mdis < maxdist[b]) {
maxdist[b] = mdis;
mdnode[b] = i;
}
} int mxdcnt = 0;
for (int i = 1; i <= cnt; ++i) if (diameter[mxdcnt] <= diameter[i]) mxdcnt = i;
for (int i = 1; i <= cnt; ++i) {
if (mxdcnt == i) continue;
G[mdnode[mxdcnt]].push_back(mdnode[i]);
G[mdnode[i]].push_back(mdnode[mxdcnt]);
vs.push_back({mdnode[mxdcnt], mdnode[i]});
} dfs1(1, 0, fdist);
int rt = 0; for (int i = 1; i <= n; ++i) if (fdist[i] > fdist[rt]) rt = i;
memset(fdist, 0, sizeof fdist); dfs1(rt, 0, fdist);
cout << *std::max_element(fdist + 1, fdist + 1 + n) << endl;
for (auto v : vs) {
cout << v.first << ' ' << v.second << endl;
}
return 0;
}