Submission #1231780

---

Source Code Expand

#include <iostream>
#include <climits>
#include <vector>
#include <cmath>

using namespace std;

void dfs(vector< vector< pair<int, int> > > &graph, vector<int> &val, int root) {

	for (int i = 0; i < graph[root].size(); ++i) {
		if (val[graph[root][i].first] == INT_MAX) {
			val[graph[root][i].first] = graph[root][i].second - val[root];
			dfs(graph, val, graph[root][i].first);
		}
	}

}

int main(void) {

	int R, C, N;
	cin >> R >> C >> N;

	vector<int> r(N), c(N), a(N);
	vector< vector< pair<int, int> > > graph(R + C);
	vector<int> val(R + C, INT_MAX);

	for (int i = 0; i < N; ++i) {
		cin >> r[i] >> c[i] >> a[i];
		--r[i]; --c[i];
		graph[r[i]].push_back(make_pair(R + c[i], a[i]));
		graph[R + c[i]].push_back(make_pair(r[i], a[i]));
	}

	for (int i = 0; i < graph.size(); ++i) {
		if (val[i] == INT_MAX && graph[i].size() > 0) {
			val[i] = 0;
			dfs(graph, val, i);
		}
	}

	/*
	for (int i = 0; i < val.size(); ++i) {
		cout << val[i] << " ";
	}
	cout << endl;
	*/

	for (int i = 0; i < N; ++i) {
		if (val[r[i]] != INT_MAX && val[R + c[i]] != INT_MAX) {
			if (val[r[i]] + val[R + c[i]] != a[i]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	int minR = INT_MAX, minC = INT_MAX;
	for (int i = 0; i < R; ++i) {
		minR = min(minR, val[i]);
	}
	for (int i = R; i < (R + C); ++i) {
		minC = min(minC, val[i]);
	}
	if (minR + minC < 0) {
		cout << "No" << endl;
		return 0;
	}

	cout << "Yes" << endl;
	return 0;

}

Submission Info

Judge Result