差分约束知识讲解
图论讲解
例题1.差分约束模板题
题意
$\space\space\space\space\space$ 给定n个不等式 求出任意一组可行解
分析
$\space\space\space\space\space$考虑构建差分约束 由题意知道 所有不等式为$A - B \leq C$ 所以 我们构建从B->A权值为C的边 通过spfa来进行是否存在判断 而对于任意一组可行解 其实就是它们本身的dist[]值(转化为图论方面考虑后 dist[]就相当于一组可行解) 最后输出即可
源码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL 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()
{
deque<int>q;
memset(dist, 0x3f, sizeof dist);
q.push_back(0);
dist[0] = 0;
st[0] = true;
while(q.size())
{
int t = q.back();
q.pop_back();
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 + 1) return false;
if(!st[j])
{
q.push_back(j);
st[j] = true;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(b, a, c);
}
for (int i = 1; i <= n; i ++ ) add(0, i, 0);
if(!spfa()) puts("NO");
else
for(int i = 1; i <= n; i ++) cout << dist[i] <<" ";
return 0;
}
例题2.小k的农场 边的差分约束判断题
题意
$\space\space\space\space\space$给定任意两个农场植株的多少关系 判断是否存在
分析
$\space\space\space\space\space$本题是边上差分约束的题 我们直接进行将不等式转化为图论建图方式
a 比 b 至少多 c ----> a - b >= c 即建立b - > a边权为c的边
a 比 b 至多多 c -----> a - b <= c <-----> b - a >= -c 即建立 a -> b边权为-c的边
a 与 b 一样多 ------> a <= b && b <= a 构建从a -> b 和 从b -> a的边权为0的边即可
$\space\space\space\space\space$本题只是一个判断问题 所以如何建立最短路或者最长路模型已无关大局 我们只需要判断是否有负环存在即可 从而输出
源码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL 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()
{
deque<int>q;
memset(dist, -0x3f, sizeof dist);
q.push_back(0);
dist[0] = 0;
st[0] = true;
while(q.size())
{
int t = q.back();
q.pop_back();
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 + 1) return false;
if(!st[j])
{
q.push_back(j);
st[j] = true;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --)
{
int x, a, b, c;
cin >> x;
if(x == 3)
{
cin >> a >> b;
add(a, b, 0), add(b, a, 0);
}
else if(x == 2)
{
cin >> a >> b >> c;
add(a, b, -c);
}
else
{
cin >> a >> b >> c;
add(b, a, c);
}
}
for (int i = 1; i <= n; i ++ ) add(0, i, 0);
if(!spfa()) puts("No");
else cout <<"Yes" <<endl;
return 0;
}
3.狡猾的商人 点的差分约束判断问题
题意
$\space\space\space\space\space$ 给定 a - > b(包括b)的判断关系 让你判断是否全部不等式成立
分析
$\space\space\space\space\space$我们发现 此题从问法上以及跟上题不同 上题是确切是两点的边的关系 而本题却包含了端点问题 而对于点 我们是没办法直接建立边的 所以我们需要进行更改下 A-> B = C我们可以更改为
sum[A - 1] -> sum[B] = C 进而完美的包含了端点问题 所以考虑
A -> B = C 建立 sum[A - 1] - Sum[B] = C && sum[B] - sum[A - 1] = C 然后转化为判断行问题 判断是否成立 即判断是否存在环
ps : 本题是多组输入情况 需特别注意对st的数组清空情况 我们知道 在纯spfa算最短路问题中st代表的是否实在队列中 所以我们在最短路求解时候不需要情况st数组 因为最后的队列一定是空的 即st都是false 然后再差分约束系统中 我们的spfa存在无解的情况 此时的退出方式是cnt >= n强行退出 所以最队列中 仍有存在元素的可能 所以在差分约束系统多组数据测试中 需要注意对st数组的清空
源码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 5010, M = 5010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int 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 ++;
}
void init()//清空数组
{
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
memset(dist, -0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
idx = 0;
}
bool spfa(int x)
{
deque<int>q;
q.push_back(x);
dist[x] = 0;
st[x] = true;
while(q.size())
{
int t = q.back();
q.pop_back();
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 + 1) return false;
if(!st[j])
{
q.push_back(j);
st[j] = true;
}
}
}
}
return true;
}
void solve()
{
init();
cin >> n >> m;
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(a - 1, b, c), add(b, a - 1, -c);
}
for(int i = 0; i <= n; i ++) add(n + 1, i, 0);
if(!spfa(n + 1))cout << "false"<<endl;
else cout << "true"<< endl;
}
int main()
{
int T;
cin >> T;
while(T --) solve();
}
例题4 .糖果 边的差分约束最值问题
题意
$\space\space\space\space\space$给定n组判断关系 要你求得满足所有人最小的需求代价
分析
$\space\space\space\space\space$ 我们通过差分约束进行判断 求得所有人的dist 最后求和即可
A == B ---- > A -> B边权为0的边 B - > A边权为0的边
A > B ----> 因为是最小需求问题 所以我们贪心的想仅仅多1个即可 则 A >= B + 1 ----> B -> A 边权为1的边
B < A -----> 同上 A -> B 边权为1的边
A >= B -----> B -> A 边权为0的边
B >= A -----> A -> B 边权为0的边
源码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL 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()
{
deque<int>q;
memset(dist, -0x3f, sizeof dist);
q.push_back(0);
// int hh = 0, tt = 1;
// q[0] = 0;
dist[0] = 0;
st[0] = true;
while(q.size())
{
int t = q.back();
q.pop_back();
//int t = q[-- tt];
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 + 1) return false;
if(!st[j])
{
q.push_back(j);
//q[tt ++] = j;
st[j] = true;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --)
{
int x, a, b;
scanf("%d%d%d", &x, &a, &b);
if(x == 1) add(b, a, 0), add(a, b, 0);
else if(x == 2) add(a, b, 1);
else if(x == 3) add(b, a, 0);
else if(x == 4) add(b, a, 1);
else add(a, b, 0);
}
for(int i = 1; i <= n; i ++) add(0, i, 1); //构建虚拟原点
if(!spfa()) puts("-1");
else
{
LL res = 0;
for(int i = 1; i <= n; i ++) res += dist[i];
cout << res << endl;
}
return 0;
}
ps 在常规的判断中 我们需要考虑所有子图是否全部连通的情况 而对于某些问题是问到 某些子图可能并不连通的情况 所以我们可以建立一个虚拟原点 进而将所有子图进行虚拟连通 进而容易判断
例题5.种树点的差分约束输出问题
题意
$\space\space\space\space\space$ 给定n个不等关系 求满足所有关系的最小贡献值
分析
$\space\space\space\space\space$ 题意说的是一种点的差分约束系统关系 所以我们仍然需要构建前缀和的形式的差分约束系统 而对于本题中 需要注意的是 我们维护的是一种前缀和关系 所以我们对于所有的 i 和[i - 1] 一定有 0<= sum[i] - sum[i - 1] <= 1
源码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int 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()
{
queue<int>q;
memset(dist, -0x3f, sizeof dist);
q.push(0);
dist[0] = 0;
st[0] = 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 + 1) return false;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return true;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(a - 1, b, c);
}
for(int i = 1; i <= n; i ++) add(i - 1, i, 0), add(i, i - 1, -1);
spfa();
cout << dist[n] << endl;
}
特注 对于任何的差分约束系统 找到所有的不等关系是关键
例题6.天平 基于floyd写法的差分约束
题意
$\space\space\space\space\space$ 有n个砝码 砝码的编重只有1、2、3三种选择 给定任意两个砝码的大小关系 求从中(不含 AB两个)任意选择两个 使得组成的重量大于 weight[A + B] 等于 和小于组成的数量有多少个
分析
$\space\space\space\space\space$ 本题不同于以往的单源最短路求最长路最短路问题 本题是求方案数 换句话说 本题需要求多源关系下的最短路最长路 所以 对于spfa来进行判断 不是特别方便 本题我们考虑floyd 我们分别构建dmax[i][j] 表示 i - j的最大值 dmin[i][j]表示i - j的最小值 通过构建等式进而计算任意两点的dmax dmin关系
A > B 我们构建 dmax[A][B] = 2, dmin[A][B] = 1;
A = B 我们构建 dmax[A][B] = 0, dmin[A][B] = 0;
A < B 我们构建 dmax[A][B] = -1, dmin[A][B] = -2;
A ？B 我们构建 dmax[A][B] = 2, dmin[A][B] = -2;
进而我们建立了初步的图的各边关系
$\space\space\space\space\space$ 其次 在建立好了图后 我们还需要进行任意两点的节点更新
对于dmax 数组 我们是求最大值 那么我们需要跑最短路 即求最小值
对于dmin 数组 我们是求最小值 那么我们需要跑最长路 即求最大值
$\space\space\space\space\space$ 在更新好节点信息后 我们需要考虑该如何计算方案数 因为数据过少 我们直接暴力+ 判断
A B 是确定选择
求大于的方案数：
A + B > i + j <---> A - i > j - B || A - j > i - B
因为我们要考虑严格小于情况 所以 只有dmin[A][i] > dmax[j][B] || dmin[A][j] > dmax[i][B] 进行计数
求少于的方案数
A + B < i + j <---> A - i < j - B || A - j < i - B
因为我们要考虑严格大于情况 所以 只有dmax[A][i] < dmin[j][B] || dmax[A][j] < dmin[i][B] 进行计数
求等于的方案数
A + B == i + j <----> A - i == j - B || A - j == i - B
因为我们要考虑严格等于 即dmax dmin均两两相等 所以
dmin[A][i] == dmax[A][i] && dmin[j][B] == dmax[j][B] && dmin[A][i] == dmin[j][B]
+(||)
dmin[A][j] == dmax[A][j] && dmin[i][B] == dmax[i][B] && dmin[A][j] == dmin[i][B] 进行计数
源码
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 55;
int dmax[N][N], dmin[N][N]; // i - j最大值 i - j最小值
int n, a, b;
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
{
if(i == k) continue;
for(int j = 1; j <= n; j ++)
{
if(i == j || i == k) continue;
dmax[i][j] = min(dmax[i][j], dmax[i][k] + dmax[k][j]);
dmin[i][j] = max(dmin[i][j], dmin[i][k] + dmin[k][j]);
}
}
}
int main()
{
cin >> n >> a >> b;
char s[N];
for(int i = 1; i <= n; i ++)
{
cin >> s;
int len = strlen(s);
for(int j = 0; j < len; j ++)
{
if(s[j] == '=' || i == j + 1) dmin[i][j + 1] = 0, dmax[i][j + 1] = 0;
else if(s[j] == '+') dmax[i][j + 1] = 2, dmin[i][j + 1] = 1;
else if(s[j] == '-') dmax[i][j + 1] = -1, dmin[i][j + 1] = -2;
else dmax[i][j + 1] = 2, dmin[i][j + 1] = -2;
}
}
floyd();
int x1 = 0, x2 = 0, x3 = 0;
for(int i = 1; i <= n; i ++)
{
if(i == a || i == b) continue;
for(int j = 1; j < i; j ++)
{
if(j == a || j == b) continue;
if(dmin[a][i] > dmax[j][b] || dmin[a][j] > dmax[i][b]) x1 ++; // A + B > i + j
if(dmin[i][a] > dmax[b][j] || dmin[i][b] > dmax[a][j]) x3 ++; // A + B < i + j
//A + B = i + j
if((dmin[a][i] == dmax[a][i] && dmin[j][b] == dmax[j][b] && dmin[a][i] == dmin[j][b] )||
(dmin[a][j] == dmax[a][j] && dmin[i][b] == dmax[i][b] && dmin[a][j] == dmax[i][b])) x2 ++;
}
}
cout << x1 <<" "<<x2 <<" "<<x3<<endl;
}
差分约束更多的是 一种求最短路的模型 而不单单是spfa的模型 对于跑图的方式要灵活应用 而不单单局限于spfa 最计算差分约束系统的时候 需要特别注意将所有的差分情况找出 针对非连通子图 需要考虑虚拟原点的建立 而对于点差分系统 和边差分系统 虚拟原点的选择又有所不同 而针对于spfa的玄学情况 有的时候deque效果由于queue的情况
xiangnangege 我爱你
巨巨 我也爱你