CF1092E. Minimal Diameter Forest

\(\texttt{Difficulty:2000}\)

题意

给定 \(n(1\le n\le 1000)\) 个点， \(m(0\le m\le n-1)\) 条边组成的森林，现在增加一些边，是森林成为一棵树，并且其直径最小，求最小直径以及方案。

思路

考虑让森林中每一棵树的直径的中点为根，然后按每棵树最长链的长度 \(l_i\) 排序，不断将根连到最长链最长的树的根上，显然这样构造可以使直径最小，直径的值为每个子树的直径的最大值，\(l\) 最长的两个子树的 \(l\) 的和 \(+1\) ，\(l\) 第二，第三长两个子树的 \(l\) 的和 \(+2\) 这三者中的最大值， \(n\) 非常小，直接暴力 \(O(n^2)\) 即可解决。

代码

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using TP = tuple<int, int, int>;
#define all(x) x.begin(),x.end()
#define mst(x,v) memset(x,v,sizeof(x))
#define mul(x,y) (1ll*(x)*(y)%mod)
#define mk make_pair
//#define int LL
//#define double LD
#define lc tr[x].ch[0]
#define rc tr[x].ch[1]
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-10;
const double pi = acos(-1);
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 300010;

int N, M, root[maxn], tot = 0;
vector<int>G[maxn], T[maxn];
bool used[maxn];
vector<PII>E;

void add_edge(int from, int to)
{
	G[from].push_back(to);
	G[to].push_back(from);
}

int dfs(int v, int p, int d)
{
	int tmp = d;
	for (auto& to : G[v])
	{
		if (to == p)
			continue;
		tmp = max(tmp, dfs(to, v, d + 1));
	}
	return tmp;
}

int D[maxn], diameter = -inf, f[maxn];

void dfs(int v, int p)
{
	used[v] = true, T[tot].push_back(v);
	for (auto& to : G[v])
	{
		if (to == p)
			continue;
		dfs(to, v);
		diameter = max(diameter, D[v] + D[to] + 1);
		D[v] = max(D[v], D[to] + 1);
	}
}

void solve()
{
	for (int i = 1; i <= N; i++)
	{
		if (!used[i])
			root[++tot] = i, dfs(i, 0), f[tot] = diameter, diameter = -inf, mst(D, 0);
	}
	for (int i = 1; i <= tot; i++)
	{
		int tmp = inf;
		for (auto& v : T[i])
		{
			int num = dfs(v, 0, 0);
			if (num < tmp)
				tmp = num, root[i] = v;
		}
		E.push_back(PII(tmp, root[i]));
	}
	int ans = 0;
	for (int i = 1; i <= tot; i++)
		ans = max(ans, f[i]);
	sort(all(E)), reverse(all(E));
	if (tot >= 3)
		ans = max(ans, max(E[0].first + E[1].first + 1, E[1].first + E[2].first + 2));
	else if (tot == 2)
		ans = max(ans, E[0].first + E[1].first + 1);
	else
		ans = max(ans, E[0].first);
	cout << ans << endl;
	for (auto& [x, y] : E)
	{
		if (y == E[0].second)
			continue;
		cout << E[0].second << ' ' << y << endl;
	}
}

int main()
{
	IOS;
	cin >> N >> M;
	int u, v;
	for (int i = 1; i <= M; i++)
		cin >> u >> v, add_edge(u, v);
	solve();

	return 0;
}