题目描述
给你一个\(n\)元一次方程，判断是否有解，方程给出的格式为 \(a-b=c\)
思路
这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集
但是因为我太懒了并且这道题目要求使用差分约束系统进行求解，于是就需要将题目转化一下
因为差分约束系统只能处理不等量关系，所以就需要使用一个不等式组进行表示，并且这个不等式组只能有一个解
于是就可以将 \(a-b=c\) 转化为\(\begin{cases}a-b\le c \\a-b \ge c\end{cases}\)
但是在差分约束系统只能处理\(\le\)的情况，所以不等式组就转化成了\(\begin{cases}a-b\le c \\b-a \le -c\end{cases}\)，
于是在输入之后就可以这样储存了：
v[a-1].push_back({b,c}),v[b].push_back({a-1,-c});
注意: \(a\) 应该\(-1\)，否则就将 \(a\) 这个月漏算了
AC Code
#include<bits/stdc++.h>
inline int read(){ //没有大用的快读
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}return x*f;
}int T,n,m,cnt[1001],dis[1001];
bool vis[1001];
struct node{
int k; //到达的点
int num; //代价
};
std::vector<node> v[1001]; //因为本人太懒，所以使用vector储存||v[i]表示从i出发的节点
inline bool spfa(int s){
std::queue<int> q;
memset(dis,0x3f,sizeof(dis)); //多测不清空,爆零见祖宗
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
dis[s]=0; //初始化
vis[s]=1;
q.push(s);
while(!q.empty()){
int top=q.front();
q.pop();
vis[top]=0;
for(node i:v[top]){
if(dis[i.k]>dis[top]+i.num){ //差分约束系统跑的是最长路
dis[i.k]=dis[top]+i.num;
if(!vis[i.k]){
q.push(i.k);
vis[i.k]=1;
cnt[i.k]++;
if(cnt[i.k]>n) //有负权环
return 0;
}
}
}
}return 1;
}int main(){
T=read();
while(T--){
n=read(),m=read();
for(int i=1,a,b,c;i<=m;++i){
a=read(),b=read(),c=read();
v[a-1].push_back({b,c}); //储存不等式
v[b].push_back({a-1,-c});
}bool flag=1;
for(int i=0;i<=n;++i){
if(spfa(i)==0){
flag=0;
break;
}
}if(flag==1)
puts("true");
else
puts("false");
for(int i=0;i<=m;i++) //多测不彻底清空=10pts
v[i].erase(v[i].begin(),v[i].end());
}return 0;
}