我居然用暴力跑过去了。。。
思路：两个区间合成一个新的区间才会产生冲突， 我们用并查集维护前缀和， 0 – n 个节点分别表示sum[ 0 ] – sum[ n ]，
d[ i ] 表示 前缀i 和它的父亲的差值， 那么对于两个在同一个并查集里的来说， 就表示这个区间的值已经知道啦， check一下
就好啦， 否则我们将不连通的两团合并。
并查集
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int>> using namespace std; const int N = + ;
const int M = 1e4 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int n, m, d[N], fa[N]; int getRoot(int x) {
if(fa[x] == x) return x;
int t = getRoot(fa[x]);
d[x] += d[fa[x]];
return fa[x] = t;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
d[i] = , fa[i] = i;
bool flag = true;
for(int i = ; i <= m; i++) {
int l, r, v;
scanf("%d%d%d", &l, &r, &v); l--;
int x = getRoot(l);
int y = getRoot(r);
if(x != y) {
fa[x] = y;
d[x] = d[r] - d[l] - v;
} else if(v != d[r] - d[l]) {
flag = false;
}
}
if(flag) puts("true");
else puts("false");
}
return ;
}
/*
*/
暴力：： 我感觉我memset -1 是有问题的 不知道咋就过了。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int>> using namespace std; const int N = + ;
const int M = 1e4 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int w, n, m, tot; struct node {
pii a; int v;
}q[];
int mp[N][N];
queue<node> que;
int main() {
scanf("%d", &w);
while(w--) {
memset(mp, -, sizeof(mp));
tot = ;
while(!que.empty()) que.pop(); scanf("%d%d", &n, &m);
for(int i = ; i < m; i++) {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
que.push(node{mk(l, r), v});
}
bool flag = true;
while(!que.empty()) {
node u = que.front(); que.pop(); if(mp[u.a.fi][u.a.se] != -) {
if(mp[u.a.fi][u.a.se] != u.v) {
flag = false;
break;
} else {
continue;
}
}
for(int i = ; i < tot; i++) {
if(q[i].a.se + == u.a.fi) {
que.push(node{mk(q[i].a.fi, u.a.se), q[i].v + u.v});
} if(u.a.se + == q[i].a.fi) {
que.push(node{mk(u.a.fi, q[i].a.se), q[i].v + u.v});
}
}
mp[u.a.fi][u.a.se] = u.v;
q[tot++] = u; }
if(flag) puts("true");
else puts("false");
}
return ;
}
/*
*/
