来一个思路比较暴力的题解吧。
暴力天下第一
思路： 这道题转化成差分约束的没想到后，我就想区间分割，把一个区间分割成两个小区间，如果两个小区间都被更新过了，那就拿来判断这两个小区间之和是否等于大区间。
具体实现：
分两步：
-
将这个区间当做一个大区间，把大区间依次分割成两个小区间，看两个小区间之和是否等于大区间。
-
将这个区间当做一个小区间，跟其他已知的可以合并的区间合并，当然，合并之前也要判断这个区间和可以与之合并的区间，合并成的大区间如果有被更新过，那就判断一下，如果没有更新过，那就更新一下。
一个疑惑：这时，肯定有人会问：为什么一个区间分成两个区间就行了？万一这个区间再分成两个小区间，这两个区间有更新过，那不是应该分成三个小区间来算了啊。我一开始也是有这样的疑惑，但是想一下，既然这个区间可以分为两个更新过的小区间了，那么在之前，我们肯定更新过这个区间了，所以不用担心分成两个小区间会错啦。
代码（注意下循环的细节）：
#include <bits/stdc++.h>
using namespace std;
int n , m , T , f;
int dis[110][110];
int main(){
cin >> T;
while(T--){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) dis[i][j] = 0x3ffffff; //初始化！！！这个是判断区间更新过没的标志
f = 0;
while(m--){
int x , y , z;
cin >> x >> y >> z;
for(int i = x; i < y; i++){ //注意是x~y-1，因为两个分成的区间不能重合
if(dis[x][i] != 0x3ffffff && dis[i + 1][y] != 0x3ffffff && dis[x][i] + dis[i + 1][y] != z){
f = 1;
cout << "false" << endl;
break;
}
}
if(f) break;
dis[x][y] = z;
for(int i = 1; i < x; i++) //这注意里的循环范围
if(dis[i][x - 1] != 0x3ffffff)
if(dis[i][y] != 0x3ffffff && dis[i][y] != dis[i][x - 1] + z) f = 1;
else dis[i][y] = dis[i][x - 1] + z;
if(f){
cout << "false" << endl;
break;
}
for(int i = y + 1; i <= n; i++) ////这注意里的循环范围
if(dis[y + 1][i] != 0x3ffffff)
if(dis[x][i] != 0x3ffffff && dis[x][i] != dis[y + 1][i] + z) f = 1;
else dis[x][i] = dis[y + 1][i] + z;
if(f){
cout << "false" << endl;
break;
}
}
if(f) continue;
cout << "true" << endl;
}
return 0;
}