/*
x[i] 表示 第i头牛位置
以求x[i]的最大值为例:所有从x[i]出发,构成的不等式链
x[i] ≤ x[j] + c[j]
≤ x[k] + c[k] + c[j]
≤ x[0] + c[1]+ c[2]+... + c[j]
= 0 + c[1]+ ... + c[j]
所计算出的上界,
最终x[i]的最大值
=所有上界的最小值
举例 x[i] ≤ 5
x[i] ≤ 2
x[i] ≤ 3
max(x[i]) = min(5,2,3) = 2
0 → 1 → 3 → 5 → ... → i
c1 c3 c5 ci-1
x[1] ≤ x[0] + c[1]
x[3] ≤ x[1] + c[3]
x[5] ≤ x[3] + c[5]
...
x[i] ≤ x[i-1] + c[i-1]
则
x[i] ≤ x[i-1] + c[i]
≤ x[i-3] + c[i-3] + c[i]
...
≤ x[0] + c[1] + c[3] + c[i-3] + c[i-1]
⭐可以发现Σc[i]就是从0→i的一条路径的长度
最大位置→不等式上界(小于等于)→上界里的最小值→最短路
x[i] ≤ x[j] + c j → i
1 每头奶牛按编号排序 i+1 → i w = 0
<=> x[i] ≤ x[i+1]
2 两者之间的距离不超过一个给定的数L
x[b]-x[a] ≤ L a → b w = L
x[b] ≤ x[a] + L
3 两者之间的距离不小于一个给定的数D
x[b]-x[a] ≥ D
x[a] ≤ x[b]-D b → a w = -D
问题1:
因为没有一个点可以无条件到所有点,
所以建超级源点0 从0向
假定所有x[i] ≤ x[0] + 0 从而可以从0向x[i]连一条长度为0的边
1 如果没有负环-有解
2 如果有负环-无解
问题2:
直接把所有点i加入队列 == 创建超级源点0
点1和点n距离是否可以无限大?
则可以把点1固定在一个位置上(选0位置)x[1] = 0,判断x[n]是否可以无限大
即求从1→n的最短路径,由于x[1]取0,则x[n]代表了n和1的最大距离,如果x[n]<INF,说明d[1→n]有限大≤x[n]
所以看x[n]是否是正无穷就可以判断x[n]是否可以无限大
问题3:
链式法则 x[i]最终会小于一个常数c
x[n]-x[1] ≤ ... ≤ c
每一个上界c都对应一条 起点x[1]=0到i的路径
求1与n的距离最大值 == 求所有上界c的最小值 == 求1~n所有路径长度的最小值
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//第一种边n条<=1000 第2、3种边各10000条
const int N = 1010, M = 21010, INF = 0x3f3f3f3f;
int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N], cnt[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
bool spfa(int size)
{
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
queue<int> q;
for(int i=1;i<=size;i++)
{
q.push(i);
dist[i] = 0;
st[i] = true;
}
while(q.size())
{
int t=q.front();
q.pop();
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])//j不在队列中
{
q.push(j);//j加入队列
st[j] = true;//标记j
}
}
}
}
return false;
}
int main()
{
cin >> n >> m1 >> m2;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++) add(i+1,i,0);//x[i] ≤ x[i+1]+0
while(m1--)
{
int a,b,c;
cin >> a >> b >> c;
if(a>b) swap(a,b);//x[b] ≤ x[a] + L a→b
add(a,b,c);
}
while(m2--)
{
int a,b,c;
cin >> a >> b >> c;//x[a] ≤ x[b]-D b→a
if(a>b) swap(a,b);
add(b,a,-c);
}
// 第一问 问这些约束有没有解 从超级源点出发==把所有点加入队列 看有没有负环
if(spfa(n)) cout << -1;
//如果不存在满足要求的方案,输出-1;
// 第二问 只需要把第一个点加入队列 求第1个点到第n个点的最短距离
else
{
spfa(1);
//如果 1 号奶牛和 N 号奶牛间的距离可以任意大,输出-2;
if(dist[n]==INF) cout << -2;
//否则,输出在满足所有要求的情况下,1 号奶牛和 N 号奶牛间可能的最大距离。
else cout << dist[n];
}
return 0;
}
这个spfa(n)有点误导性,我还以为是从n出发呢想了半天,然后才发现Spfa代码里面写的是全部加入队列,,我还是太naive了,不过谢谢大佬,写的很好!
也可以只加n的,不需要全部都入队
只加n的话不会造成无法遍历所有点的问题么?
dalao, swap的作用是什么呀
我的理解是距离是相对距离,本题中我们将x1作为初始参照点,将x1的位置记为0,距离x1就是d,所以设置差分约束条件的时候我们就不用绝对值了,让更靠右的减去更靠左的就行
但是我测试了一下,不交换也能AC,如果你找到原因了请@一下我
为什么我把所有的点加入队列,只把1号奶牛距离为0,也能一遍spfa过
因为第一个spfa就是用来判断是否有负换的,所以你直接加入1也是可以的
这句话x[i] ≤ x[i+1]为什么不能保证n是超级源点呢?
因为这些点都是有约束的,题目条件,你不能保证一定存在一个点是超级源点
不对啊,开始时已经把所有点根据x[i] ≤ x[i+1]连在一起了,则n肯定是超级源点
感谢,看明白了,差分约束也不是很难了,感谢!!!
应该是
以求x[i]的最大值为例:所有最终到x[i],构成的不等式链
把?