ABC087D （套路题）

难度1

套路题

对于多个\(x_{i}-y{i}=k_{i}\)的约束条件，考虑连边再dfs一下，如果冲突就exit

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
struct node{
	long long to,val;
}p;
long long T,n,m,x,y,z,dis[100005],tot[100005];
bool vis[100005];
vector<node>v[100005];
void dfs(int u,int tot){
	dis[u]=tot;
	vis[u]=true;
	for(int i=0;i<v[u].size();i++){
		int to=v[u][i].to,val=v[u][i].val;
		if(vis[to]==true){
			if(val+tot!=dis[to]){
				cout<<"No"<<endl;
				exit(0);
			}
		}
		else dfs(to,tot+val);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	if(n==1){
		cout<<"Yes"<<endl;
		return 0;
	}
	for(long long i=1;i<=m;i++){
		cin>>x>>y>>z;
		p.to=x;
		p.val=z;
		v[y].push_back(p);
		p.to=y;
		p.val=-z;
		v[x].push_back(p);
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==false){
			dfs(i,0);
		}
	}
	cout<<"Yes"<<endl;
	
	return 0;
}