https://beta.atcoder.jp/contests/arc090/tasks/arc090_b
解説
https://beta.atcoder.jp/contests/arc090/submissions/2029402
重要な考察があり、「1つ数を決めるとそれと連結の座標の数が全て決まる」
座標のまだ数が決まってない所の1つを0にして、
有向辺(a,b,c)を順にたどって行く場合は「col[b] = col[a] + c」、
逆に辿っていく場合は「col[a] = col[b] - c」で数を決めていく。
このように構築していく仮定で矛盾が発生したら"No"を返す。
全て問題無く構築できたら"Yes"を返す。
int N, M; vector<pair<int, int>> E[201010]; vector<pair<int, int>> EE[201010]; int vis[201010], col[201010]; //--------------------------------------------------------------------------------------------------- #define no "No" #define yes "Yes" string solve() { rep(i, 0, N) if (!vis[i]) { col[i] = 0; vis[i] = 1; queue<int> que; que.push(i); while (!que.empty()) { int q = que.front(); que.pop(); fore(p, E[q]) { if (vis[p.first]) { if (col[q] + p.second != col[p.first]) return no; } else { col[p.first] = col[q] + p.second; vis[p.first] = 1; que.push(p.first); } } fore(p, EE[q]) { if (vis[p.first]) { if (col[q] - p.second != col[p.first]) return no; } else { col[p.first] = col[q] - p.second; vis[p.first] = 1; que.push(p.first); } } } } return yes; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, M) { int a, b, c; cin >> a >> b >> c; a--; b--; E[a].push_back({ b, c }); EE[b].push_back({ a, c }); } cout << solve() << endl; }