题解：P11644 【MX-X8-T3】「TAOI-3」地地爱打卡

~~特判有点恶心。~~

分析

结论：如果

x

和路径长度的奇偶性相同或是在

s,t

所在联通快中含有一个奇环则合法。

证明：因为可以在一条路上来回走，所以可以将快乐值凑到

x

，由于一个数异或偶数个

1

还是这个数本身，所以最终的能量值也可以凑到

0

。又因为奇数长度的环可以改变路径长度的奇偶性，所以如果图中有奇环那么一定合法。

做两遍 dfs 即可，第一遍 dfs 判断连通性，第二遍 dfs 找奇环，注意特判孤立点。

CPP

#include <bits/stdc++.h>
using namespace std;
vector<int>g[200005];
int shu[200005], vis[200005], cnt;
int vi[200005], dis[200005], ji[200005];

void dfs(int x) {
	if (vis[x])
		return;
	vis[x] = 1;
	for (int y : g[x]) {
		shu[y] = cnt;
		dfs(y);
	}
}

void df(int x, int fa) {
	vi[x] = 1;
	for (int y : g[x]) {
		if (y == fa)
			continue;
		if (!vi[y])
			dis[y] = dis[x] + 1, df(y, x);
		else if (abs(dis[x] - dis[y]) % 2 == 0)
			ji[shu[x]] = 1;
	}
}

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i])
			shu[i] = ++cnt, dfs(i), df(i, 0);
	while (q--) {
		int s, t, x;
		cin >> s >> t >> x;
		if (shu[s] != shu[t])
			cout << "expand";
		else if (s == t && g[s].size() == 0 && x != 0)
			cout << "expand";
		else {
			if (abs(dis[s] - dis[t]) % 2 == x % 2 || ji[shu[s]])
				cout << "tribool";
			else
				cout << "expand";
		}
		cout << "\n";
	}
}

题解：P11644 【MX-X8-T3】「TAOI-3」地地爱打卡

文章操作

分析

相关推荐

评论

题解：P11644 【MX-X8-T3】「TAOI-3」地地爱打卡