Submission #899631

---

Source Code Expand

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;

using namespace std;

int R, C, N;
vector<ll> w;

struct E{
    int to, cost;
    E(int t, int c): to(t), cost(c) {};
};
vector<vector<E> > edge;
ll rmin, cmin;

bool dfs(int v) {
    if(v < R) rmin = min(rmin, w[v]);
    else cmin = min(cmin, w[v]);
    REP(i, edge[v].size()) {
        E e = edge[v][i];
        if(w[e.to] != -1) {
            if(w[v]+w[e.to]!=e.cost) return false;
        } else {
            w[e.to] = e.cost - w[v];
            if(!dfs(e.to)) return false;
        }
    }
    return true;
}

int main(void) {
    int tr, tc, ta;
    cin >> R >> C >> N;

    edge.resize(R+C);
    REP(i, N) {
        cin >> tr >> tc >> ta;
        tr--; tc--;
        edge[tr].push_back(E(R+tc, ta));
        edge[R+tc].push_back(E(tr, ta));
    }

    w.resize(R+C);
    w.assign(R+C, -1);

    REP(i, R+C) {
        if(w[i] != -1 || edge[i].size() == 0) continue;
        w[i] = 0;
        rmin = numeric_limits<ll>::max();
        cmin = numeric_limits<ll>::max();
        if(!dfs(i) || rmin+cmin < 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Submission Info

Judge Result