ACM_JLINE.

差分约束

差分约束
字数统计: 911阅读时长: 4 min
2019/01/29 Share

[题目连接]洛谷 BZOJ1731
推荐洛谷 因为好多OJ这一题数据较水（亲测）

题意
正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。有编号为 1 2…N 的 N头奶牛 (2 ≤ N ≤ 1000)。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 ML 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 MD 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 。(1 ≤ ML,MD ≤ 1e4)

请计算：如果满足上述所有条件，1 号奶牛和 N 号奶牛之间的距离最大为多少。

输出格式
一行，一个整数。如果没有合法方案，输出 -1. 如果有合法方案，但 1 号奶牛可以与 N 号奶牛相距无穷远，输出 -2. 否则，输出 1 号奶牛与 N 号奶牛间的最大距离。

题解
很明显的差分约束了
根据题目，可列出以下式子：( u < v )
dis[v] − dis[u] ≤ L ⇒ dis[v] − dis[u] ≤ L ⇒ 从u到v连一条边权为L的边 add(u, v, L)
dis[v] − dis[u] ≥ D ⇔ dis[u] − dis[v] ≤ −D ⇒ dis[v] − dis[u] ≥ D ⇔ dis[u] − dis[v] ≤ −D ⇒ 从v到u连一条边权为-D的边 add(v, u, -D)

这些是比较容易想到的条件了， 但是 根据题意 dis[i] <= dis[i+1] 也就是说需要add(i, i-1, 0)。 然后一般性水点的数据没问题了，可是万一图上是存在负环的，可是你选择的起点，正常是 1 号点是独立于负环的， 也就是说万一起点根本没有进入负环，你的答案就出错了， 正确答案应该是 -1 。 所以还要设一个 0 号点， 与所有点建立 0 边， 第一次跑 SPFA 以 0 号点为起点，如果有负环，直接输出 -1 就行了， 否则以 1 号点为起点再跑一遍 SPFA，就能得到正确答案了。（有点意思）

Code block

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 4e5+5;
const ll INF = 1e12+5;
int head[N], Next[N], ver[N], cnt, ans[N], vis[N];
ll dis[N], edge[N];
int n, L, D, x, y, z;

void add(int x, int y, int z)
{
	ver[++cnt] = y;
	edge[cnt] = z;
	Next[cnt] = head[x];
	head[x] = cnt;
}
ll spfa(int x)
{
	for(int i = 0; i <= n; i++) dis[i] = INF;
	memset(ans, 0, sizeof(ans));
	memset(vis, 0, sizeof(vis));
	dis[x] = 0; vis[x] = 1; 
	queue <int> q;
	q.push(x);
	while(!q.empty())
	{
		int x = q.front(); q.pop(); vis[x] = 0;
		for(int i = head[x]; i; i = Next[i]){
			int y = ver[i], w = edge[i];
			if(dis[y] > dis[x] + w)
			{
				ans[y]++;
				//cout << y << endl;
				if(ans[y] == n) return -1;
				dis[y] = dis[x] + w;
				if(!vis[y]) {
					q.push(y);
					vis[y] = 1;
				}		
			}	
		}
	}
	if(dis[n] == INF) return -2;
	return dis[n];
}

int main()
{
	scanf("%d%d%d", &n, &L, &D);
	for(int i = 2; i <= n; i++) add(i, i-1, 0);
	for(int i = 1; i <= n; i++) add(0, i, 0);
	for(int i = 0; i < L; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	for(int i = 0; i < D; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		add(y, x, -z);
	}
	if(spfa(0) == -1) printf("%d\n", -1);
	else{
		ll Ans = spfa(1);
		printf("%lld\n", Ans);
	}  
	return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/01/29/DAY4/

发表日期：January 29th 2019, 8:30:33 pm

更新日期：January 29th 2019, 8:30:56 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路