借用这道题复习一下差分约束

题目大意就是,一个长度为$n$的数列,有$m$个限制条件,每个限制条件有$s,t,w$三个整数,表示数列第$s$项到第$t$项的和为$w$。

思路也比较简单,首先这样的题目一看就是差分约束,然后因为差分约束是形如$x_i-x_j\leq c$的式子,所以想办法把题目给的条件转化为差的形式,就变成前缀和,$s_i-s_{j-1}=c$,把每个条件的$j-1$向$i$连接一条边,边权为$c$,但是这样可以发现并没有什么用,因为区间和为$w$还包含一个信息就是$s_{j-1}-s_i=-c$,因此再从$i$向$j-1$连一条边,边权为$-c$,这样如果有正环,每个$s$就可以不断更新,也就是一个假的账本(可以画个图来理解一下),反之则为真的账本。

P.S. 注意数组大小,边数最多可能有2100条($n\leq 100,m\leq 1000$)

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

int w, n, m;
struct Edge{
    int to, nxt, w;
}e[4009];
int head[4009], tot;
int d[4009], cnt[4009];
bool vis[4009];

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

bool spfa(){
    queue<int> q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    q.push(0);
    d[0] = 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, w = e[i].w;
            if(d[y] > d[x] + w){
                d[y] = d[x] + w;
                cnt[y]++;
                if(cnt[y] > n + 1){
                    return 0;
                }
                if(!vis[y]){
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
        vis[x] = 0;
    }
    return 1;
}

int main(){
    scanf("%d", &w);
    while(w--){
        memset(head, 0, sizeof(head));
        memset(e, 0, sizeof(e));
        tot = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++){
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            y++;
            add(x, y, -w);
            add(y, x, w);
        }
        for(int i = 1; i <= n; i++){
            add(0, i, 0);
        }
        if(spfa()) printf("true\n");
        else printf("false\n");
    }
    return 0;
}
Last modification:April 9th, 2020 at 11:30 pm