CF1103C Johnny Solving (Codeforces Round #534 (Div. 1)) 思维+构造

题目传送门

https://codeforces.com/contest/1103/problem/C

题解

这个题还算一个有难度的不错的题目吧。

题目给出了两种回答方式：

找出一条长度 \(\geq \frac nk\) 的路径；
找出 \(k\) 个简单环，满足长度不是 \(3\) 的倍数，并且每个环至少存在一个点不在别的环中。

很显然题目并不是要你随便挑一种回答方式开始单独研究。最有可能的情况是两种回答方式可以替补。

如果我们随便作出原图的一棵生成树，如果最长的路径长度 \(\geq \frac nk\)，那么我们可以直接输出。否则，很容易发现，这棵树上至少有 \(k\) 个叶子。

很容易把 \(k\) 个叶子往第二种回答方式中的 \(k\) 个环上联想。但是第二个回答方式中的几个条件我们还都要满足。

对于“每个环至少存在一个点不在别的环中”这个条件，等价于就是说，每一个叶子不会和其余的叶子有连边。dfs 树可以保证这个性质，同时 dfs 树还可以保证，每一个点出来的非树边一定是返祖边。那么，建立 dfs 树以后，每个环就是每一个叶子和它的一些祖先之间的事情了。

接着考虑环的长度不是 \(3\) 的倍数的这个条件。

首先，我们不妨假设叶子 \(x\) 连向的两条返祖边指向的点分别为 \(x\) 的祖先为 \(f_1\) 和 \(f_2\)。

那么我们得到了三个环 \(x \to f_1 \to x\)，\(x\to f_2 \to x\)，\(f_1\to f_2 \to x\)。

然后三条路径的长度为别为 \(dep_x - dep_{f_1} + 1\)，\(dep_x - dep_{f_2} + 1\)，\(dep_{f_1} - dep_{f_2} + 2\)。

如果 \(dep_x - dep_{f_1} + 1\) 和 \(dep_x - dep_{f_2} + 1\) 都是 \(3\) 的倍数（否则输出其中的一个就可以了），那么就是说 \((dep_x - dep_{f_1}) - (dep_x - dep_{f_2}) + 2 = dep_{f_1} - dep_{f_2} + 2\) 模上 \(3\) 应该是 \(2\)。

也就是说，上面的三个环中至少存在一个环的长度不是 \(3\) 的倍数。输出哪一个即可。

时间复杂度 \(O(n+m)\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 2.5e5 + 7;

const int M = 5e5 + 7;

int n, m, k, nk;

int fz[N][3], f[N], chk[N], vis[N], dep[N];

struct Edge { int to, ne; } g[M << 1]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

inline void dfs(int x, int fa = 0) {

	f[x] = fa, vis[x] = 1, dep[x] = dep[fa] + 1;

	int &c = chk[x] = 1;

	for fec(i, x, y)

		if (!vis[y]) c = 0, dfs(y, x);

		else if (y != fa && fz[x][0] < 2) fz[x][++fz[x][0]] = y;

}

inline void work() {

	dfs(1);

	for (int i = 1; i <= n; ++i) if (dep[i] >= nk) {

		puts("PATH");

		printf("%d\n", dep[i]);

		for (int x = i; x; x = f[x]) printf("%d%c", x, " \n"[!f[x]]);

		return;

	}

	puts("CYCLES");

	int cnt = 0;

	for (int i = 1; i <= n; ++i) if (chk[i]) {

		++cnt;

		if (dep[fz[i][1]] < dep[fz[i][2]]) std::swap(fz[i][1], fz[i][2]);

		if ((dep[i] - dep[fz[i][1]]) % 3 != 2) {

			int ans = 0;

			for (int x = i; x != f[fz[i][1]]; x = f[x]) ++ans;

			printf("%d\n", ans);

			for (int x = i; x != f[fz[i][1]]; x = f[x]) printf("%d%c", x, " \n"[x == fz[i][1]]);

		} else {

			if ((dep[i] - dep[fz[i][2]]) % 3 != 2) {

				int ans = 0;

				for (int x = i; x != f[fz[i][2]]; x = f[x]) ++ans;

				printf("%d\n", ans);

				for (int x = i; x != f[fz[i][2]]; x = f[x]) printf("%d%c", x, " \n"[x == fz[i][2]]);

			} else {

				int ans = 1;

				for (int x = fz[i][1]; x != f[fz[i][2]]; x = f[x]) ++ans;

				printf("%d\n", ans);

				for (int x = fz[i][1]; x != f[fz[i][2]]; x = f[x]) printf("%d ", x);

				printf("%d\n", i);

			}

		}

		if (cnt >= k) return;

	}

	assert(cnt >= k);

}

inline void init() {

	read(n), read(m), read(k), nk = (n - 1) / k + 1;

	int x, y;

	for (int i = 1; i <= m; ++i) read(x), read(y), adde(x, y);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

CF1103C Johnny Solving (Codeforces Round #534 (Div. 1)) 思维+构造

题目传送门

题解

最新文章

热门文章