HDU 5915 The Fastest Runner Ms. Zhang （CCPC2016 长春 E题，分类讨论 + 求字典序最小的直径 + 数据结构寻找最小值）

题目链接 CCPC2016 Changchun Problem E

题意给定一个$n$个点$n$条边的无向图，现在从某一点$s$出发，每个点都经过一遍，最后在$t$点停止，经过的边数为$l$

　　求字典序最小的三元组$(l, s, t)$

设环的长度为$c$，

当$s$和$t$在同一棵子树上的时候，$s$到$t$的路径上的边和环上的边只要走一次，其他边都要走两次，那么答案为$2n - c - len$

$len$为$s$到$t$的路径的长度；

当$s$和$t$不在同一棵子树上的时候，设$s$走到环上的第一个点为$u$，$t$走到环的第一个点为$v$。

那么这个时候考虑每条边走过的次数。

对于不在环上的边，从$s$到$u$，从$v$到$t$的路径只要走一次，其余的边都要走两次。

对于在环上的边，从$u$到$v$的路径只要走一次，其余的部分都要走两次，但是有一条边不用经过（一次都不用走）

那么答案为$2n - 2 - len(s, u) - len(u, v) - len(v, t)$；

对于第一种情况，我们对环上每棵树都求一条字典序最小的直径然后更新答案即可。

对于第二种情况，我们需要最大化$len(s, u) + len(u, v) + len(v, t)$的值。

考虑每个环上的点，显然$s$和$t$的最佳选择都是从这个点往里走可以走到的最深的点。

设环上的点依次排列为：$a_{1}， a_{2}， a_{3}， ......， a_{cnt}$。

设每个环上的点往子树方向走能走到的最深的深度为$c_{1}， c_{2}， c_{3}， ......， c_{cnt}$

倍长a数组和c数组，对于每个位置$i(cnt < i <= 2 * cnt)$，找到一个最佳的点$j(i - cnt + 1 <= j <= i - 1)$。

使得$i - j + c[j] + c[i] = i + c[i] + (c[j] - j)$的值最大。

那么用单调队列维护$c[j] - j$的最大值即可。我为了方便偷懒用了ST表。

#include <bits/stdc++.h>

using namespace std;

#define	rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	fi		first

#define	se		second

#define	MP		make_pair

typedef long long LL;

typedef pair <int, int> PII;

const int N = 1e5 + 10;

struct node{

	int x, y;

} b[N << 1];

node f[N << 1][20];

int T;

int n, cnt;

int a[N], isroot[N], father[N], vis[N];

int len, l, r;

int lg[N << 1];

int m;

int ca = 0;

vector <int> v[N];

pair <int, PII> ans;

PII  c[N];

int get_circle(int x){

	vis[x] = 1;

	for (auto u : v[x]){

		if (u == father[x]) continue;

		father[u] = x;

		if (vis[u]){

			cnt = 0;

			int w = x;

			while (w ^ u){

				a[++cnt] = w;

				isroot[w] = cnt;

				w = father[w];

			}

			a[++cnt] = u;

			isroot[u] = cnt;

			return 1;

		}

		if (get_circle(u)) return 1;

	}

	return 0;

}

inline node mx(const node &a, const node &b){

	if (a.x == b.x){

		if (a.y < b.y) return a;

		else return b;

	}

	if (a.x > b.x) return a; else return b;

}

void dfs(int x, int fa, int dep){

	if ((dep > len) || (dep == len && x < l)){

		len = dep;

		l   = x;

	}

	for (auto u : v[x]){

		if (u == fa || isroot[u]) continue;

		dfs(u, x, dep + 1);

	}

}

void dfs2(int x, int fa, int dep, int extra){

	if ((dep > len) || (dep == len && x < r)){

		len = dep;

		r   = x;

	}

	for (auto u : v[x]) if ((u != fa) && (!isroot[u] || u == extra)){

		dfs2(u, x, dep + 1, extra);

	}

}

inline node solve(int l, int r){

	int k = lg[r - l + 1];

	return mx(f[l][k], f[r - (1 << k) + 1][k]);

}

int main(){

	lg[1] = 0;

	rep(i, 2, 2e5) lg[i] = lg[i >> 1] + 1;

	scanf("%d", &T);

	while (T--){

		scanf("%d", &n);

		if (n == 2) while (1);

		rep(i, 0, n + 1){

			v[i].clear();

			isroot[i] = 0;

			father[i] = 0;

			vis[i] = 0;

		}

		cnt = 0;

		rep(i, 1, n){

			int x, y;

			scanf("%d%d", &x, &y);

			v[x].push_back(y);

			v[y].push_back(x);

		}

		father[1] = 0;

		get_circle(1);

		memset(c, -1, sizeof c);

		ans = MP(1e9, MP(-1, -1));

		rep(i, 1, cnt){

			len = -1;

			l = -1;

			r = -1;

			dfs(a[i], 0, 0);

			c[i] = MP(len, l);

			len = -1;

			dfs2(l, 0, 0, a[i]);

			if (l > r) swap(l, r);

			ans = min(ans, MP(2 * n - len - cnt, MP(l, r)));

		}

		rep(i, 1, cnt){

			b[i] = {c[i].fi - i + 1, c[i].se};

			b[i + cnt] = {c[i].fi - (i - 1 + cnt), c[i].se};

		}

		m = cnt << 1;

		memset(f, 0, sizeof f);

		rep(i, 1, m) f[i][0] = b[i];

		rep(j, 1, 18){

			rep(i, 1, m){

				if ((i + (1 << j) - 1) <= m) f[i][j] = mx(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

			}

		}

		rep(i, cnt + 1, m){

			node now = solve(i - cnt + 1, i - 1);

			int ll = now.y, rr = c[i - cnt].se;

			if (ll > rr) swap(ll, rr);

			int ret = c[i - cnt].fi + i - 1 + (now.x);

			ans = min(ans, MP(2 * n - 2 - ret  ,   MP(ll, rr)  )    );

		}

		printf("Case #%d: %d %d %d\n", ++ca, ans.fi, ans.se.fi, ans.se.se);

	}

	return 0;

}

巴特西

HDU 5915 The Fastest Runner Ms. Zhang （CCPC2016 长春 E题，分类讨论 + 求字典序最小的直径 + 数据结构寻找最小值）

最新文章

热门文章