Problem Statement

There are N people standing on the x-axis. Let the coordinate of Person i be x_i. For every i, x_i is an integer between 0 and 10⁹ (inclusive). It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people. The i-th piece of information has the form (L_i,R_i,D_i). This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_Ri−x_Li=D_i holds.

It turns out that some of these M pieces of information may be incorrect. Determine if there exists a set of values (x₁,x₂,…,x_N) that is consistent with the given pieces of information.

Constraints

• 1≤N≤100 000
• 0≤M≤200 000
• 1≤L_i,R_i≤N (1≤i≤M)
• 0≤D_i≤10 000 (1≤i≤M)
• L_i≠R_i (1≤i≤M)
• If i≠j, then (L_i,R_i)≠(L_j,R_j) and (L_i,R_i)≠(R_j,L_j).
• D_i are integers.

Sample Input 1

3 3

1 2 1

2 3 1

1 3 2

Sample Output 1

Yes

Some possible sets of values (x₁,x₂,x₃) are (0,1,2) and (101,102,103).

Sample Input 2

3 3

1 2 1

2 3 1

1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x₃−x₁=2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3

2 1 1

2 3 5

3 4 2

Sample Output 3

Yes

Sample Input 4

10 3

8 7 100

7 9 100

9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes

题意：给定有N个人，M条信息。每条信息：L，R，D，表示第R个人在第L个人的右边距离为D。求根据这M条信息判断安排是否成立。
题解：本来以为可以在线一条一条输入输入信息的同时判断是否合法，好像是不可以。答案说是构成图，然后DFS每一个节点。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<cstdio>

 using namespace std;

 const int maxn = 1e5 + ;

 typedef long long ll;

 vector<pair<int, int> > e[maxn];

 ll dis[maxn];

 bool vis[maxn];

 int n, m,flag=;

 void dfs(int x)

 {

     vis[x] = ;

     for (int i = ; i < e[x].size(); i++)

     {

         pair<int, int> cur=e[x][i];

         if (vis[cur.first]) {

             if (dis[cur.first] - dis[x] != cur.second) {

                 flag = ; break;

             }

         }

         else {

             dis[cur.first] = dis[x] + cur.second;

             dfs(cur.first);

         }

     }

 }

 int main()

 {

     cin >> n >> m;

     memset(vis, , sizeof(vis));

     for (int i = ; i < m; i++) {

         int l, r, d;

         cin >> l >> r >> d;

         e[l].push_back({ r,d });

         e[r].push_back({ l,-d });

     }

     flag = ;

     for (int i = ; i <n; i++) {

         if (!vis[i])

             dfs(i);

         if (flag) {

             break;

         }

     }

     if (flag) {

         cout << "No" << endl;

     }

     else

         cout << "Yes" << endl;

     return ;

 }