并查集60求调
查看原帖
并查集60求调
1141947
jqdlk楼主2024/3/9 10:46
#include<bits/stdc++.h>
#define MAX_N 200010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
//并查集基本实现
int par[MAX_N];
int n, m,q;
ll d[MAX_N];
void init()
{
	for (int i = 1; i <=n; i++)
	{
		par[i] = i;
	}
}
int find(int x)
{
	if (par[x] != x)
	{
		int t = par[x];
		par[x] = find(par[x]);
		d[x] += d[t];
	}
	return par[x];
}
void unit(int l, int r,int s)
{
	int pl, pr;
	pl = find(l);
	pr = find(r);
	par[pl] = pr;
	d[pl] = d[r]-d[l]-s;
}
bool same(int x, int y)
{
	return find(x) == find(y);
}
int main()
{
	cin >> n >> m >> q;
	init();
	ll a, b, c;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		unit(a-1, b, c);
	}

	while (q-->0)
	{	int r, l;
		cin >> l>> r;
		if (same(l - 1, r))
			cout << d[r] - d[l - 1] << endl;
		else
			cout << "UNKNOWN" << endl;
	}
	return 0;
}
2024/3/9 10:46
加载中...