代码求调(codeforces886 div4)
  • 板块学术版
  • 楼主LonginusMonkey
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/23 22:17
  • 上次更新2023/11/3 08:01:00
查看原帖
代码求调(codeforces886 div4)
326254
LonginusMonkey楼主2023/7/23 22:17

昨天晚上写了个带权并查集,但是一直没有调出来

他第二个点总是显示的是runtime error,求调!

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int index, len;
}fa[400100];
node find(int n) {
	if(n == fa[n].index) {
		return fa[n];
	}
	else
	{
		node temp = fa[n];
		fa[n] = find(fa[n].index);
		fa[n].len += temp.len;
		return fa[n];	
	}
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		int n, m;
		cin >> n >> m;
		for(int i=0; i<=n; ++i) {
			fa[i].index = i;
			fa[i].len = 0;
		}
		bool bl = 0;
		for(int i=1; i<=m; ++i) {
			int x, y, z;
			cin >> x >> y >> z;
			if(z < 0) {
				swap(x, y);
				z=-z;
			}
			node tempa = find(x), tempb = find(y);
			int fax = tempa.index, fay = tempb.index, lenx = tempa.len, leny = tempb.len;
//			int fax = find(x).index, fay = find(y).index, lenx = find(x).len, leny = find(y).len;
			if(fax == fay) {
				if(leny == lenx + z) {
					continue;
				}
				else
				{
					bl = 1;
					break;
				}
			}
			else
			{
				if(lenx + z > leny) {
					fa[fay].index = fax;
					fa[fay].len = lenx+z-leny;
				}
				else
				{
					fa[fax].index = fay;
					fa[fax].len = leny-z-lenx;
				}
			}
			if(bl) {
				break;
			}
		}
		if(bl) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
		}
	}
	return 0;
}
2023/7/23 22:17
加载中...