AT_codefestival_2016_qualA_d 题解

考虑充分条件，对于 a_{i,j},a_{i,j+1},a_{i+1,j},a_{i+1,j+1}，则要求的充分条件是 a_{i,j+1}-a_{i,j}=a_{i+1,j+1}-a_{i+1,j}。就是两列之间差值相同。

考虑如果有两个位置 (a,i,w_1),(a,j,w_2)，则从 i\to j 连 w_2-w_1 的边，表示第 j 列比第 i 列多 w_2-w_1。

建图，对于一个连通块，找到一个基准点，算出每个点到这个点的相对大小，然后把所有点跑一遍暴力判断看看会不会弄成负数就好了。

需要思考的问题是对于一个位置，行、列都没有出现过，此时相当于差可以任意选择。所以不同连通块之间是不影响的。

考虑这是模拟赛题，保险起见行、列都跑了一次，其实只跑一个方向就是充要条件了。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define NO {puts("No");exit(0);}
using namespace std;
const int N = 1e5 + 5;
int n, m, k, x;
struct node{
    int a, b, c;
}a[N];
inline void chkmin(int &x, int y){
    if(x > y) x = y;
}
struct Graph{
    vector<pii> G[N];
    int dist[N], n, vis[N], minn[N], cnt;
    inline void addedge(int x, int y, int z){
        G[x].push_back({y, z});
        G[y].push_back({x, -z});
        // if(x == 12 || y == 12) cerr << x << ' ' << y << ' ' << z << endl;
    }
    inline void dfs(int x){
        vis[x] = cnt;
        chkmin(minn[cnt], dist[x]);
        for(pii e : G[x]){
            if(vis[e.fi]){
                if(dist[e.fi] != dist[x] + e.se) NO;
                continue ;
            }
            dist[e.fi] = dist[x] + e.se;
            dfs(e.fi);
        }
    }
    inline void solve(){
        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                dist[i] = 0;
                cnt++;
                dfs(i);
            }
        }
    }
}L, C;
signed main(){
    // freopen("zibi.in", "r", stdin);
    // freopen("zibi.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &m, &k);
    for(int i = 1; i <= k; i++){
        scanf("%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c);
    }
    sort(a + 1, a + k + 1, [&](node x, node y){
        if(x.a == y.a) return x.b < y.b;
        return x.a < y.a;
    });
    L.n = m, C.n = n;
    for(int i = 1; i <= k; i++){
        if(a[i].a == a[i - 1].a){
            L.addedge(a[i - 1].b, a[i].b, a[i].c - a[i - 1].c);
        }
    }
    L.solve();
    // cerr << endl;
    sort(a + 1, a + k + 1, [&](node x, node y){
        if(x.b == y.b) return x.a < y.a;
        return x.b < y.b;
    });
    for(int i = 1; i <= k; i++){
        if(a[i].b == a[i - 1].b){
            C.addedge(a[i - 1].a, a[i].a, a[i].c - a[i - 1].c);
            if(a[i].a == 5387 || a[i].a == 41257){
                // cerr << "test : " << a[i].a << ' ' << a[i].b << ' ' << a[i].c << endl;
                // cerr << "test2 : " << a[i - 1].a << ' ' << a[i - 1].b << ' ' << a[i - 1].c << endl;
            }
        }
    }
    C.solve();
    // for(int i = 1; i <= m; i++){
    //     if(C.vis[i] == 5219){
    //         cerr << i << ' ' << C.dist[i] << endl;
    //     }
    // }
    // cerr << endl;
    for(int i = 1; i <= k; i++){
        x = L.minn[L.vis[a[i].b]] - L.dist[a[i].b];
        // cerr << a[i].b << ' ' << L.vis[a[i].b] << ' ' << a[i].c << ' ' << x << endl;
        if(x + a[i].c < 0) NO;
        x = C.minn[C.vis[a[i].a]] - C.dist[a[i].a];
        // cerr << a[i].a << ' ' << a[i].b << ' ' << C.vis[a[i].a] << ' ' << a[i].c << ' ' << x << endl;
        if(x + a[i].c < 0) NO;
    }
    puts("Yes");
    return 0;
}