请问差分约束为什么只能用最长路,而不能用最短路?

回复帖子

@C C A  2021-07-22 18:22 回复

$\quad \rm RT$

$\quad$这是最短路的代码,只有 $70\rm pts.$

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

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
    to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d", &op, &u, &v);
        if (op == 1) add(u, v, 0), add(v, u, 0);
        else if (op == 2) add(v, u, -1);
        else if (op == 3) add(u, v, 0);
        else if (op == 4) add(u, v, -1);
        else if (op == 5) add(v, u, 0);

    }
    rep(i, 1, n) to[++tot] = i, Next[tot] = last[0], last[0] = tot;

    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0, in[0] = true, Q.push(0);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), in[u] = false;
        if (++cnt[u] > 1000) puts("-1"), exit(0);
        for (int i = last[u]; i; i = Next[i])
            if (dis[to[i]] > dis[u] + W[i]) {
                dis[to[i]] = dis[u] + W[i];
                if (!in[to[i]]) Q.push(to[i]);
            }
    }

    long long ans = 0; int Min = 1e9;
    rep(i, 1, n) Min = min(Min, dis[i]);
    rep(i, 1, n) ans += dis[i] - Min;
    printf("%lld\n", ans + n);

    return 0;
}

$\quad$这是最长路的代码,$\rm AC$ 了

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

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
    to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d", &op, &u, &v);
        if (op == 1) add(u, v, 0), add(v, u, 0);
        else if (op == 2) add(u, v, 1);
        else if (op == 3) add(v, u, 0);
        else if (op == 4) add(v, u, 1);
        else if (op == 5) add(u, v, 0);

    }
    for (int i = n; i >= 1; i--) add(0, i, 1);

    memset(dis, 128, sizeof dis);
    dis[0] = 0, in[0] = true, Q.push(0);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), in[u] = false;
        if (++cnt[u] > 3500) puts("-1"), exit(0);
        for (int i = last[u]; i; i = Next[i])
            if (dis[to[i]] < dis[u] + W[i]) {
                dis[to[i]] = dis[u] + W[i];
                if (!in[to[i]]) Q.push(to[i]);
            }
    }

    long long ans = 0;
    rep(i, 1, n) ans += dis[i];
    printf("%lld\n", ans);

    return 0;
}
@天命之路 2021-07-22 18:53 回复 举报
if (++cnt[u] > 1000) puts("-1"), exit(0);
 if (++cnt[u] > 3500) puts("-1"), exit(0);

卡界卡得不一样,显然一个WA一个AC

如果你用最长路,边权都非负,跑遍dijkstra 稳过

SPFA 可能被卡

换成stack 大概率更慢

@天命之路 2021-07-22 21:36 回复 举报

哦对,说错了,不能用dij

那个稳过的算法是这样的:

边权都非负的时候,跑最长路

先用tarjan 把环缩掉,可以证明如果有解,环内边权均为0,故这个强连通分量内所有的 $dist$ 值都相同。

然后拓扑排序,在新图上求 $dist$ (令 $dist[0]=0$,其余为 $-inf$ ,常规跑即可)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。