@[toc]
差分约束
差分约束的两个应用
求不等式组的可行解
:sailboat:步骤1:把每个x[i] <= x[j] + c[k]
这样的不等式转化为一条从x[j]
走到x[i]
长度为c[k]
的边。
:waning_gibbous_moon:步骤2:然后在这个图上找一个超级源点,使得该源点一定可以遍历到所有边
源点需要满足的条件:从源点出发,一定可以走到所有的边,否则如果有一条边走不到的话,那么就无法确定两个点的约束条件。若一个点走不到无所谓,因为它不受任何约束。
:neutral_face: 步骤3:从源点走一遍单源最短路
如下图所示,如果存在负环:
:ghost: 步骤4:求完单源最短路之后:
结果1:如果存在负环,则原不等式组一定无解
结果2:如果没有负环,则 dist[i]
就是原不等式组的一个可行解
如何求最大值或者最小值,这里的最值指的是每个变量的最值
结论:如果求的是最小值
,则应该求最长路
;如果求的是最大值
,则应该求最短路
。
问题:如何转化 xi≤c
,其中 c
是一个常数,这类的不等式。
方法:建立一个超级源点0,然后建立 0 -> i
的边,长度是 c
即可。
求最大值:
求所有从x出发,构成的多个形如以下的不等式链:
$$ xi≤xj+c1≤xk+c2+c1≤⋅⋅⋅≤x0+c1+c2+⋅⋅⋅+cm(x0=0) $$
所计算出来的上界,最终x[i]
的值等于所有上界的最小值。
这里所有上界的最小值可以理解这么一个例子:
把上述转换成图论的问题,就是求 dist[i]
的最小值,即最短路
求解
求 xi
的最小值
时则完全相反,求一个形如如下不等式链
所计算出的下界
,最终在所有下界里取最大值
$$ xi≥xj+c1≥xk+c2+c1≥⋅⋅⋅≥x0+c1+c2+⋅⋅⋅+cm(x0=0) $$
转换成图论
的问题,就是求 dist[i]
的最大值
,即最长路
求解
例题
AC1169 糖果
:jack_o_lantern: 题目:
:rainbow: 思路
本道题求的是最小值,所以也就是求最长路,其中最关键的就是如何建图:
- x == 1,A == B ,A >= B -> A >= B + 0, A <= B -> B >= A + 0
- x == 2,A < B -> B >= A + 1
- x == 3, A >= B -> A >= B + 0
- x == 4,A > B -> A >= B + 1
- x == 5, A <= B -> B >= A + 0
由于本题中可能存在正环,所以我们需要用spfa来求最长路,这里用一个不会TLE的判负环方法,那就是把SPFA算法中的循环队列改为栈,这样对于遇到的负环,就不会加入队尾,知道再次遍历完整个队列才去算他。遇到负环会直接在栈顶连续入栈出栈,直到判断他的cnt[i] >= n+1(因为多了一个0号点,所以有n+1个点,一个点最多只能更新n次)
,即发现负环
:horse: 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
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()
{
mset(dist, -0x3f);
dist[0] = 0;
stack<int> q;
q.push(0);
st[0] = 1;
while (q.size())
{
int t = q.top();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; 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 + 1)
return false;
if (!st[j])
{
q.push(j);
st[j] = 1;
}
}
}
}
return true;
}
void solve()
{
mset(h, -1);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int t, a, b;
cin >> t >> a >> b;
if (t == 1)
{
add(a, b, 0);
add(b, a, 0);
}
else if (t == 2)
add(a, b, 1);
else if (t == 3)
add(b, a, 0);
else if (t == 4)
add(b, a, 1);
else
add(a, b, 0);
}
for (int i = 1; i <= n; i++)
add(0, i, 1);
bool ok = spfa();
if (ok)
{
ll ans = 0;
for (int i = 1; i <= n; i++)
ans += dist[i];
cout << ans;
}
else
cout << -1;
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
while (T--)
solve();
return 0;
}
还有一种方法可以求
:wedding: 思路:tarjan
我们可以求出每一个强连通分量,然后进行缩点,如果发现有正环就表示无解。tarjan
算法是可以保证 O(n+m)
的,所以用这个算法求一定不会卡。
:cactus: 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 6, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int Size[N];
int id[N];
int scc_cnt;
int h[N], hs[N], e[M], w[M], ne[M], idx;
void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
scc_cnt++;
int y;
do
{
y = stk[top--];
id[y] = scc_cnt;
Size[scc_cnt]++;
in_stk[y] = false;
} while (y != u);
}
}
void solve()
{
mset(h, -1);
mset(hs, -1);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int t, a, b;
cin >> t >> a >> b;
if (t == 1)
{
add(h, a, b, 0);
add(h, b, a, 0);
}
else if (t == 2)
add(h, a, b, 1);
else if (t == 3)
add(h, b, a, 0);
else if (t == 4)
add(h, b, a, 1);
else
add(h, a, b, 0);
}
for (int i = 1; i <= n; i++)
add(h, 0, i, 1);
tarjan(0);
bool ok = false; //判断是否存在正环
for (int i = 0; i <= n; i++)
{
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
int a = id[i];
int b = id[k];
if (a == b)
{
if (w[j] > 0)
{
ok = true;
break;
}
}
else
{
add(hs, a, b, w[j]);
}
}
}
if (ok)
{
puts("-1");
return;
}
for (int i = scc_cnt; i >= 1; i--)
{
for (int j = hs[i]; j != -1; j = ne[j])
{
int k = e[j];
dist[k] = max(dist[i] + w[j], dist[k]);
}
}
ll ans = 0;
for (int i = 1; i <= scc_cnt; i++)
ans += (ll)Size[i] * dist[i];
cout << ans;
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
while (T--)
solve();
return 0;
}
AcWing 362. 区间
:ocean:题目
:cactus:思路:差分约束
本题保证是一定有解的,我们可以将区间上的每一个点都填上。
对于本题中我们需要满足一个区间内填的整数和不超过某个数,那么可以用前缀和的思想。因为前缀和中s[0] =0
,所以需要将整个区间都加上1,这样区间范围就由[0,50000] -> [1, 50001]
,最后结果是不变的。
我们用s[i]
来表示1~i
中选了多少个数,我们要求就是s[50001]
的最小值,所以我们需要求最长路。
对于S,S需要满足如下条件:
s[i] >= s[i-1]
s[i] - s[i-1] <= 1
==>s[i-1] >= s[i] - 1
- 区间
[a,b]
内至少有c个数,==》s[b] - s[a - 1] >= c
==>s[b] >= s[a-1] + c
这里我们的0号点就是超级源点,它可以到1,1到2,... 一直可以走到终点
:rabbit2: 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int h[N], e[M], w[M], ne[M], idx;
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()
{
mset(dist, -0x3f);
dist[0] = 0;
queue<int> q;
q.push(0);
st[0] = 1;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] < dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = 1;
}
}
}
}
return true;
}
void solve()
{
mset(h, -1);
cin >> n;
for (int i = 1; i <= n; i++)
{
int c, a, b;
cin >> a >> b >> c;
a++;
b++;
add(a - 1, b, c);
}
for (int i = 1; i <= 5e4 + 1; i++)
{
add(i - 1, i, 0);
add(i, i - 1, -1);
}
spfa();
cout << dist[50001];
return;
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
while (T--)
solve();
return 0;
}
AC1170. 排队布局
:joy: 题目
本题是让我们求最大值,所以是求最短路。
- B - A <= L <==> B <= A + L
- B - A >= D <==> A <= B - D
s[i] - s[i-1] >= 0
<==>s[i - 1] <= s[i] + 0
两头牛之间的距离至少是0
我们要求的答案:
- 不存在满足要求的方案 <==> 有负环 :输出-1
- 距离无穷大:输出-2
- 有最短路:输出
如何判断负环,上糖果那道题一样,设置一个超级源点跑一遍最短路看入队次数是否超过n
:dango: 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m1, m2;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
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 s)
{
mset(dist, 0x3f);
mset(cnt, 0);
mset(st, 0);
stack<int> q;
for (int i = 1; i <= s; i++)
{
q.push(i);
dist[i] = 0;
st[i] = 1;
}
while (q.size())
{
int t = q.top();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; 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 false;
if (!st[j])
{
q.push(j);
st[j] = 1;
}
}
}
}
return true;
}
void solve()
{
mset(h, -1);
cin >> n >> m1 >> m2;
for (int i = 1; i < n; i++)
add(i + 1, i, 0);
while (m1--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
while (m2--)
{
int a, b, c;
cin >> a >> b >> c;
add(b, a, -c);
}
// 先判断是否出现了负环
if (!spfa(n))
{
cout << -1;
}
else
{
spfa(1);
if (dist[n] == inf)
cout << -2;
else
cout << dist[n];
}
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
while (T--)
solve();
return 0;
}
AcWing 393. 雇佣收银员
:first_quarter_moon_with_face: 题目
:dagger: 思路
r[i]
表示i
时刻来了多少顾客
nums[i]
表示i`时刻最多有多少个收银员
x[i]
表示i
时刻选择了多少个收银员
我们可以列出不等式:
0<=x[i]<=nums[i]
x[i-7] + x[i-6] + ... x[i] >= r[i]
:一个收银员可以工作8个小时,一个顾客可以被在i
时刻来了那么它就可以被[i-7,i]
这段时间内开始工作的收银员服务。
这里我们可以用前缀和的思想,用s[i]
表示[1, i]
这一时间段内总共来了多少个收银员,那么上面的不等式就可以转换为:
0 <= s[i] - s[i - 1] <= nums[i]
s[i] - s[i - 8] >= r[i]
这里我们需要注意一个细节,如果一个服务员是在20点上的班,那么它可以工作到早上3点。所以这里我们需要分别判断
- i >= 8 :
s[i] - s[i - 8] >= r[i]
- i < 8 :
s[i] + s[24] - s[i + 16] >= r[i]
我们可以发现,i<8
的不等式中有三个变量,我们又要求s[24]
,所以我们可以枚举s[24]
的值,找到符合所有不等式的最小值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int r[N];
int num[N];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build(int c)
{
mset(h, -1);
idx = 0;
for (int i = 1; i <= 24; i++)
{
add(i - 1, i, 0);
add(i, i - 1, -num[i]);
}
for (int i = 8; i <= 24; i++)
add(i - 8, i, r[i]);
for (int i = 1; i < 8; i++)
{
add(i + 16, i, -c + r[i]);
}
// s24 == c
add(0, 24, c);
add(24, 0, -c);
}
bool spfa(int c)
{
build(c);
// 求最长路
mset(dist, -0x3f);
mset(cnt, 0);
mset(st, 0);
stack<int> q;
q.push(0);
dist[0] = 0;
st[0] = 1;
while (q.size())
{
int t = q.top();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; 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] >= 25)
return false;
if (!st[j])
{
q.push(j);
st[j] = 1;
}
}
}
}
return true;
}
void solve()
{
mset(num, 0);
for (int i = 1; i <= 24; i++)
cin >> r[i];
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
num[x + 1]++;
}
int l = 0, r = n;
while (l < r)
{
int mid = (l + r) >> 1;
if (spfa(mid))
r = mid;
else
l = mid + 1;
}
if (!spfa(r))
cout << "No Solution\n";
else
cout << r << '\n';
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
:lollipop: 有疑问欢迎评论区留言哦