分析题意:
给你一组不等式,让你求
1.是否有解,可以转化成求是否存在负环
2.$\ 1\ 和\ n\ $间距离是否可以任意大,即求$|x_n−x_1|$最大值也就是求上界是否存在
3.$\ 1\ 和\ n\ $之间可能的最大距离,即求$|x_n−x_1|$最大值也就是求上界,即$|x_n−x_1| ≤ c$求最小的$c$
解:
问题1直接找或者建超级源点跑找负环的算法就行了,本题点$\ n\ $能到所有点(见下面建边第一条)
问题2和3转化成求$|x_n−x_1|$上界是否存在,存在的话是多少,即求最短路
本题有条件$x_n \geq x_1$(见下面建边第一条),所以$|x_n−x_1| \leq c$化简为$x_n \leq x_1 + c$,即求$\ 1\ 到\ n\ 的最短路$
根据题意列的不等式和求最短路建边:
1.如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标
$$x_i \leq x_{i + 1} \quad (\ i+1\ 到\ i\ 边权为\ 0\ 的边)$$
2.$\ A\ 和\ B\ 间至多间隔\ L$
\begin{equation}
|x_b - x_a| \leq L \\
x_b \leq x_a + L \ (a < b) \quad (\ a\ 到\ b\ 边权为\ L\ 的边) \\
x_a \leq x_b + L \ (b < a) \quad (\ b\ 到\ a\ 边权为\ L\ 的边)
\end{equation}
3.$\ A\ 和\ B\ 间至少间隔\ L$
\begin{equation}
|x_b - x_a| \geq L \\
x_a \leq x_b - L \ (a < b) \quad (\ b\ 到\ a\ 边权为\ -L\ 的边) \\
x_b \leq x_a - L \ (b < a) \quad (\ a\ 到\ b\ 边权为\ -L\ 的边)
\end{equation}
注:
利用上述建边后的图,求n到1的最短路求的是$x_1 \leq x_n + c$,变化成$|x_n - x_1| \geq -c$,求的是最小的c,也就是最大的-c,求的是1到n之间距离的下界
对于$|x_n - x_1| \geq d$
$x_n \geq x_1 + d$ 最长路建边求最长路时求1到n的最长路,最大的d
$x_1 \leq x_n - d$ 最短路建边求最短路时求n到1的最短路,最小的-d,即最大的d
最长路和最短路建边后的图,所有边方向相反,大小相反
理由:
对于$|x_b - x_a| \leq L$,其他同理
最短路建边:$x_b \leq x_a + L \ (a < b) \quad (\ a\ 到\ b\ 边权为\ L\ 的边)$
最长路建边:$x_b - L \leq x_a \ (a < b) \quad (\ b\ 到\ a\ 边权为\ -L\ 的边)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 21010;
int n, ml, mr;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], q[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa(int x)
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt= 0;
dist[x] = 0;
q[tt ++] = x;
while (hh != tt)
{
int t = q[hh ++];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j])
{
q[tt ++] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> ml >> mr;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++) add(i + 1, i, 0);
while (ml --)
{
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
add(a, b, c);
}
while (mr --)
{
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
add(b, a, -c);
}
if (spfa(n)) puts("-1");
else
{
spfa(1);
if (dist[n] == 0x3f3f3f3f) puts("-2");
else printf("%d\n", dist[n]);
}
return 0;
}