洛谷 P5590 赛车游戏

Vanilla_chan · 2021-03-31 09:06:22 · 题解

P5590 赛车游戏

Problem

给一张有向图，请给每一条边赋上边权w\in[1,9]使得每一条1\to n的路径的长度相等。

Solution

先来点前置知识：差分约束。

简述

将很多对变量之间的差\le c的关系转化为图论，再用图论算法来求解这个不等式组的解。

步骤

对于x_j-x_i\le k，我们会发现它类似最短路网络中的三角不等式d_v-d_u\le w_{<u,v>}.我们将每一个变量看作一个点，再建立一个超级原点x_0并向每一个点连一条权值为0的有向边。对于每一个不等式x-y\le k\to x\le y+k，我们连一条由y指向x，权值为k的有向边，然后跑最短路。

在建图的过程中要先关注具体问题，若求的是两个变量差的最大值，那么将所有不等式转变成"<="的形式并且在建图后求最短路，反之在转换成">="的形式，并且求最长路。

另外，如果有负环，那么该不等式组无解。我们只要放心大胆的跑SPFA就好。如果一个点入队次数大于n，说明存在负环。

Code

见模板题

好。接下来回到这道题。

给一张有向图，请给每一条边赋上边权w\in[1,9]使得每一条1\to n的路径的长度相等。

如果始终想的是如何让所有1\to n的路径相等那么就想错方向了。

在一个图中进行最短路的时候，dis_x+w_{x\to v}=dis_v说明dis_v-dis_x=w_{x\to v}\in[1,9]，这样我们才可以用差分约束系统进行求解。