题解 P5590 【赛车游戏】

· · 题解

P5590 赛车游戏 题解

本文同步发布于 My Blog

写在前面

众所周知这是一篇题解，当然这也是一篇经验的总结。

它源自于洛谷月赛，传送门：P5590 赛车游戏

笔者写下这篇题解，一是希望自己这次的错误不要再犯，二是希望能帮助大家。

题解部分

题意大致可以概括为：给你 n 个点 m 条边的 一张图，你需要给每条边加上边权，使得1-n的所有路径的长度均相等。

现在感觉问题简单多了，我们可以想到暴力地添加边权（反正边权也只有 1 \text{-} 9）

很明显上面的办法是不能拿满分的。并且我拿到本题并没有想过要打暴力。

我们假设这张图存在两个顶点 u,v，它们之间的边权为 val(u,v)。

那么就有：dis[u]+val(u,v)=dis[v] （dis数组是节点1到其他点的路径长度最值）

至于这个最值是什么，稍后再解答。

我提出了上面那个式子，那么很明显我们要求的是 val(u,v)，这东西一定满足 1≤val(u,v)≤9

好了，现在变形一下式子：1≤val(u,v)=dis[v]-dis[u]≤9，看出来什么了吗？

你仔细看看：1≤dis[v]-dis[u]≤9，差分约束？

没错，就是差分约束，约束条件：

\left\{\begin{aligned} dis[v]-dis[u]≥1 \\dis[u]-dis[v]≥-9 \\\end{aligned}\right.

根据差分约束的经验，我们从 u 向 v 连一条边权为 1 的边， 从 v 向 u 连一条边权为 -9的边跑最长路即可。

如果 SPFA 跑出来的是负环，那么无解，否则每条边的长度为 dis[v]-dis[u]（现在可见 dis 代表最长路径）

细节实现

首先你知道知道我们只要 1~n 的路径，所以我们正反图各跑一遍，把那些 1 不能到达的节点和 n 不能到达的节点剔除掉，剩下的节点就是我们真正要进行约束的节点，而那些被剔除掉的节点对应的边可以随便乱赋值的啦……

这个操作可以通过两遍 dfs 或者 bfs 实现。但是由于我只建了一张图，所以我采用正反边异或后编号相等的原则。

这样我只写了一个 dfs 函数

void check(int x, bool *flag, int op) {
    if(flag[x]) return;
    flag[x] = 1;
    for(int i = head[x]; i; i = Next[i]) {
        if(~i & op) continue;
        int y = ver[i];
        check(y, flag, op);
    }
}

但是 op 只有 0 和 1，与上 0 ……崩崩

正确的写法：

void check(int x, bool *flag, int op) {
    if(flag[x]) return;
    flag[x] = 1;
    for(int i = head[x]; i; i = Next[i]) {
        if((i & 1) == op) continue;
        int y = ver[i];
        check(y, flag, op);
    }
}

然后要注意特判 1 不能到 n 的情况，也要输出 -1。

接下来看代码理解吧

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

/*
约束条件
d[a] + val<a,b> = d[b]
1 <= d[b] - d[a] <= 9
*/

const int N = 1e5 + 10, M = N << 2;
int head[N], Next[M], ver[M];
int edge[M], cnt = 1;
struct rec {
    int x, y;
} e[M >> 1];

void add(int x, int y, int v) {
    ver[++cnt] = y, edge[cnt] = v;
    Next[cnt] = head[x], head[x] = cnt;
}

void Add(int x, int y) {
    add(x, y, 0), add(y, x, 0);
}

bool v1[N], v2[N];
void check(int x, bool *flag, int op) {
    if(flag[x]) return;
    flag[x] = 1;
    for(int i = head[x]; i; i = Next[i]) {
        if((i & 1) == op) continue;
        int y = ver[i];
        check(y, flag, op);
    }
}

int dis[N], tot[N];
bool v[N];
void spfa(int n) {
    memset(dis, ~0x7f, sizeof dis), dis[1] = 0;
    queue<int> q;
    q.push(1), v[1] = 1;

    while(q.size()) {
        int x = q.front();
        q.pop(), v[x] = 0;

        for(int i = head[x]; i; i = Next[i]) {
            int y = ver[i], val = edge[i];
            if(dis[y] < dis[x] + val) {
                dis[y] = dis[x] + val;
                if(!v[y]) q.push(y), tot[y]++, v[y] = 1;
                if(tot[y] > n) puts("-1"), exit(0);
            }
        }
    }
    if(dis[n] < 0) puts("-1"), exit(0);
}

void clear() {
    memset(head, 0, sizeof head);
    memset(Next, 0, sizeof Next);
    memset(ver, 0, sizeof ver);
    cnt = 0;
}

bool is[N];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &e[i].x, &e[i].y);
        Add(e[i].x, e[i].y);
    }
    check(1, v1, 1), check(n, v2, 0);
    for(int i = 1; i <= n; i++)
        if(v1[i] && v2[i]) is[i] = 1;

    is[1] = is[n] = 1;
    clear();
    for(int i = 1; i <= m; i++) {
        if(is[e[i].x] && is[e[i].y]) {
            add(e[i].x, e[i].y, 1);
            add(e[i].y, e[i].x, -9);
        }
    }
    spfa(n);
    printf("%d %d\n", n, m);
    for(int i = 1; i <= m; i++) {
        printf("%d %d ", e[i].x, e[i].y);
        if(is[e[i].x] && is[e[i].y])
            printf("%d\n", dis[e[i].y] - dis[e[i].x]);
        else printf("1\n");
    }
    return 0;
}
End

当时考试脑抽没写出来，然后因为那个 op 改了一个下午……

跪了 Orz