Submission #1113171

---

Source Code Expand

#include<bits/stdc++.h>

#define FOR(i, a, b) for(int(i)=(a);(i)<(b);(i)++)
#define REP(i, n) FOR((i), 0, (n))

#define RFOR(i, b, a) for(int(i)=(b); (i)>=(a); (i)--)
#define RREP(i, n) FOR((i), (n), 0)

#define pb push_back
#define mp make_pair 

using namespace std;

const int INF=INT_MAX/4;
const int MOD=1000000007;
const double EPS=1e-14;

const bool debug_flag=true;

void debug(string str){
	if(debug_flag){
		cout<<str<<endl;
	}
}

void debugs(string str){
	if(debug_flag){
		cout<<str;
	}
}

class Edge{
public:
	int to, cost;
};

vector<vector<Edge> > edge;
vector<bool> used;
vector<int> value;

void dfs(int n, int v){
	used[n]=true;
	value[n]=v;
	REP(i, edge[n].size()){
		if(!used[edge[n][i].to]){
			dfs(edge[n][i].to, edge[n][i].cost-v);
		}
	}
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout.precision(10);

	int R, W, N;
	cin>>R>>W;
	cin>>N;
	edge.resize(R+W);
	used.resize(R+W);
	value.resize(R+W);

	int r, w, a;
	Edge ee;
	REP(i, N){
		cin>>r>>w>>a;
		r--;
		w--;
		ee.to=R+w;
		ee.cost=a;
		edge[r].pb(ee);
		ee.to=r;
		edge[R+w].pb(ee);
	}

	REP(i, R+W){
		if(!used[i]){
			dfs(i, 0);
		}
	}

	REP(i, R){
		REP(j, edge[i].size()){
			if(value[i]+value[edge[i][j].to]!=edge[i][j].cost){
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	
	int m1=INF, m2=INF;
	REP(i, R){
		if(value[i]<m1){
			m1=value[i];
		}
	}

	FOR(i, R, R+W){
		if(value[i]<m2){
			m2=value[i];
		}
	}

	if(m1+m2<0){
		cout<<"NO"<<endl;
	}else{
		cout<<"Yes"<<endl;
	}

	return 0;
}

Submission Info

Judge Result