[NOIP2018 TG D2T1]旅行

题目大意：$NOIP\;TG\;D2T1$

题解：一棵树的很简单，第一个点一定是$1$，只需要对每个节点，找最小的没有访问过的节点访问即可，我写的是$O(n\log_2n)$。

考虑基环树的部分，一个显然的想法是枚举一条环上的边，然后删掉，跑树的部分，复杂度为$O(mn\log_2n)$，明显过不了。于是考场上的我开始发扬人类智慧，发现有一个环上的边可以不经过，可以找这一条边的贡献，若不经过这条边的下一位和经过这条边的下一位进行比较，若不经过较优则不经过这条边。

出来问了一下，发现可以先把每个点的子树的儿子排序，再枚举删除的边可以做到$O(nm)$，可以过。

卡点：考试时写的代码可能会“多删除”几条边导致出错，并且仅当环上的点为当前的节点儿子中最大的节点时才会断这条边，而考场上没考虑到。考场上写了一个环的部分分，没有考虑到走回去的情况（如果不写，我的那个假的程序是可以跑对的，也就是说我白白丢了$12$分还花了时间，自闭了）

C++ Code：

#include <cstdio>

#include <algorithm>

#include <vector>

#define maxn 5010

inline int min(int a, int b) {return a < b ? a : b;}

int head[maxn], cnt = 1;

struct Edge {

	int to, nxt;

	bool can;

} e[maxn << 1];

inline void add(int a, int b) {

	e[++cnt] = (Edge) {b, head[a], true}; head[a] = cnt;

}

int n, m;

namespace Work1 {

	int ans[maxn], idx;

	void dfs(int u, int fa = 0) {

		ans[++idx] = u;

		std::vector<int> V; V.clear();

		for (int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (v != fa) V.push_back(v);

		}

		std::sort(V.begin(), V.end());

		for (std::vector<int>::iterator it = V.begin(); it != V.end(); it++) {

			dfs(*it, u);

		}

	}

	int main() {

		for (int i = 1, a, b; i < n; i++) {

			scanf("%d%d", &a, &b);

			add(a, b);

			add(b, a);

		}

		dfs(1);

		for (int i = 1; i <= n; i++) {

			printf("%d", ans[i]);

			putchar(i == n ? '\n' : ' ');

		}

		return 0;

	}

}

namespace Work2 {

	int C;

	int ans[maxn], p[maxn], idx;

	bool vis[maxn];

	int res[maxn], scc;

	int in_C = 0;

	bool used_C = false;

	void dfs(int u, int fa = 0, int last = n + 1) {

		vis[u] = true;

		ans[++idx] = u;

		std::vector<int> V; V.clear();

		for (int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (!vis[v] && v != fa) V.push_back(v);

		}

		std::sort(V.begin(), V.end());

		for (std::vector<int>::iterator it = V.begin(); it != V.end(); it++) if (!vis[*it]) {

			if (res[u] == res[*it]) {

				if (in_C == u) used_C = true;

				if (!in_C) in_C = u;

				if (used_C) {

					dfs(*it, u, n + 1);

				} else {

					if ((it + 1) == V.end()) {

						if (*it < last) dfs(*it, u, last);

						else used_C = true;

					} else dfs(*it, u, *(it + 1));

				}

			} else dfs(*it, u, n + 1);

		}

	}

	int DFN[maxn], low[maxn];

	int S[maxn], top;

	void tarjan(int u, int father = 0) {

		DFN[u] = low[u] = ++idx;

		S[++top] = u;

		int v;

		for (int i = head[u]; i; i = e[i].nxt) if (i ^ father ^ 1) {

			v = e[i].to;

			if (!DFN[v]) {

				tarjan(v, i);

				low[u] = min(low[u], low[v]);

			} else low[u] = min(low[u], DFN[v]);

		}

		if (DFN[u] == low[u]) {

			scc++;

			do {

				v = S[top--];

				res[v] = scc;

			} while (v != u);

		}

	}

	inline bool check() {

		for (int i = 1; i <= n; i++) if (ans[i] != p[i]) {

			return p[i] < ans[i];

		}

		return false;

	}

	void dfs2(int u, int fa = 0) {

		p[++idx] = u;

		std::vector<int> V; V.clear();

		for (int i = head[u]; i; i = e[i].nxt) if (e[i].can) {

			int v = e[i].to;

			if (v != fa) V.push_back(v);

		}

		std::sort(V.begin(), V.end());

		for (std::vector<int>::iterator it = V.begin(); it != V.end(); it++) {

			dfs2(*it, u);

		}

	}

	int main() {

		for (int i = 0, a, b; i < n; i++) {

			scanf("%d%d", &a, &b);

			add(a, b);

			add(b, a);

		}

		tarjan(1);

		for (int i = 1; i <= n; i++) ans[i] = n;

		if (n < 500) {

			for (int i = 2; i <= cnt; i += 2) {

				int u = e[i ^ 1].to, v = e[i].to;

				if (res[u] == res[v]) {

					idx = 0;

					e[i].can = e[i ^ 1].can = false;

					dfs2(1);

					if (check()) {

						for (int j = 1; j <= n; j++) ans[j] = p[j];

					}

					e[i].can = e[i ^ 1].can = true;

				}

			}

			for (int i = 1; i <= n; i++) {

				printf("%d", ans[i]);

				putchar(i == n ? '\n' : ' ');

			}

			return 0;

		}

		for (int i = 2; i <= cnt; i += 2) {

			int u = e[i ^ 1].to, v = e[i].to;

			if (res[u] == res[v]) {

				C = res[u];

				break;

			}

		}

		idx = 0;

		dfs(1);

		for (int i = 1; i <= n; i++) {

			printf("%d", ans[i]);

			putchar(i == n ? '\n' : ' ');

		}

		return 0;

	}

}

int main() {

	scanf("%d%d", &n, &m);

	if (n - 1 == m) {

		return Work1::main();

	}

	if (n == m) {

		return Work2::main();

	}

	return 0;

}

巴特西

[NOIP2018 TG D2T1]旅行

最新文章

热门文章