第四个点RE,求解第四个点是啥数据
查看原帖
第四个点RE,求解第四个点是啥数据
298165
黑白铅笔楼主2020/11/30 17:17
#include <cstdio>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
using namespace std;

#define forp(i,a,n) for(int i=a;i<=n;i++)
typedef long long LL;
typedef unsigned long long ULL;

template<typename T>
inline void read(T& t) {
	memset(&t, 0, sizeof(t));
	bool f = false;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') f = true;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		t = (t << 1) + (t << 3) + (ch - '0');
		ch = getchar();
	}

	if (f) t = -t;
}

const int MAXN = 100005;
const int MAXM = 200005;
const int MOD = 1000000007;

struct Edge {
	int from;
	int to;
	int next;
	int v;
}edge[MAXM];

bool operator < (const Edge& e1, const Edge& e2) {
	return e2.v > e1.v;
}

int N, M, K;
int ans[MAXN];

// 链式前向星 
int head[MAXN], gcnt = 1;
Edge G[MAXM * 2];
void addstar(int a, int b, int v) {
	G[gcnt].to = b;
	G[gcnt].v = v;
	G[gcnt].next = head[a];
	head[a] = gcnt++;
}

// 并查集 
int fa[MAXN];
int find(int x) {
	int r = x;
	while (fa[r] != r) r = fa[r];
	fa[x] = r;
	return r;
}

// 最小生成树 
void mst() {
	sort(edge+1, edge + M + 1);
	int cnt = 0;
	forp(i, 1, M) {
		if (cnt == N) break;
		if (find(edge[i].from) != find(edge[i].to)) {
			addstar(edge[i].from, edge[i].to, edge[i].v);
			addstar(edge[i].to, edge[i].from, edge[i].v);
			fa[find(edge[i].to)] = find(edge[i].from);
			cnt++;
		}
	}
}

// 深搜
void dfs(int n, int fa) {
	for (int j = head[n]; j; j = G[j].next) {
		if (G[j].to == fa) continue;
		ans[G[j].to] = ans[n] ^ G[j].v;
		dfs(G[j].to, n);
	}
}

void resolve()
{
	read(N); read(M); read(K);
	forp(i, 1, N) fa[i] = i;
	forp(i, 1, M) read(edge[i].from), read(edge[i].to), read(edge[i].v);

	mst();

	dfs(1, 0);

	forp(i, 1, K) {
		int l, r;
		read(l); read(r);
		printf("%d\n", ans[l] ^ ans[r]);
	}
}

int main()
{
	//	freopen("test.in", "r", stdin);
	//	freopen("test.out", "w", stdout);

	resolve();
	return 0;
}

2020/11/30 17:17
加载中...