这又是一道差分约束

和P2294基本上没区别,代码甚至和上一个文章的代码一模一样,记一下思路吧

一个矩阵,n行m列,有两种操作,某行或者某列同时加减一个数,然后有些位置有固定的数,给出某些位置的数,问能否通过一些操作使得这些位置上的数能满足要求。

给出第x行第y列的数为c,就相当于第x行的操作数加上(减去)第y行操作数等于c就行了,正好符合差分约束条件,判个负环就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, k;
struct Edge{
    int to, nxt;
    ll w;
}e[4000009];
int head[2009], tot;
ll dis[2009];
int cnt[2009];
bool vis[2009];

void add(int x, int y, ll w){
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].nxt = head[x];
    head[x] = tot;
}

bool spfa(){
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    dis[0] = 0;
    q.push(0);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 1;
        for(int i = head[x]; i; i = e[i].nxt){
            int y = e[i].to;
            ll w = e[i].w;
            if(dis[y] > dis[x] + w){
                dis[y] = dis[x] + w;
                cnt[y]++;
                if(cnt[y] > n + m){
                    return 0;
                }
                if(!vis[y]){
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
        vis[x] = 0;
    }
    return 1;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &m, &k);
        memset(head, 0, sizeof(head));
        memset(e, 0, sizeof(e));
        tot = 0;
        for(int i = 1; i <= k; i++){
            int x, y;
            ll w;
            scanf("%d%d%lld", &x, &y, &w);
            y = n + y;
            add(x, y, w);
            add(y, x, -w);
        }
        for(int i = 1; i <= n + m; i++) add(0, i, 0);
        if(spfa()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
Last modification:April 11th, 2020 at 12:40 am