差分约束模板题
差分约束的模板请参考 AcWing 362. 区间
推导过程
由于牵扯到 $[i−8+1,i]$ 这段区间的和的约束,所以用前缀和更好表达一些
$Si$表示$0 ~ i$时刻的存在的收银员人数
根据我们定义的这个数组,可以结合题目构造出以下条件:
(整个时段可以看成是一个环,24时连在0时后面)
1. 当$i >= 8$ , $[i - 7 , i]$这个区间的时刻需要至少大于$p[i]$的人数:
$S_{i} - S_{i-8} >= p[i] =========> S_{i} >= S_{i-8} + p[i]$
2. 当$1 <= i <= 7$ , 因为覆盖的范围可以到$S_{24}$ ~ $S_{(24-(8-i))}$和$0 $~$S_{i}$,所以要两段拼接起来:
前半段$S_{i}$ , 后半段$S_{24} - S_{(16+i)}$ , 即为$S_{i} >= p[i] + S_{16+i} - S_{24}$
- 注意因为形式不符合标准格式,所以枚举$S_{24}$的所有取值,将$S_{24}$当成常数处理
3.前缀和数组需要满足:
$S_{i} >= S_{i-1}$
4.前提是i时段的人数不能超过题目给出的i时段的人数:
$S_{i-1} >= S_{i} - num[i]$
5.承接第二条,单独从不等式分离出来的$S_{24}$自身也要连一条边:
$S_{24} = c =======> S_{24} >= c , c >= S_{24}$
最后
那么根据以上条件,就可以建图求最长路,最后的$dist[]$数组就是我们想要求的前缀和数组$S[]$
差分约束
c++代码
/*
(前缀和思想)
定义一个数组S:Si表示0 ~ i时刻的存在的收银员人数
p[i]:为题目中i时刻需要的人数
num[i]:为i时刻题目给出的收银员人数
根据我们定义的这个数组,可以结合题目构造出以下条件:
(整个时段可以看成是一个环,24时连在0时后面)
1. i >= 8 , [i - 7 , i]这个区间的时刻需要至少大于p[i]的人数:
Si - Si-8 >= p[i] =====> Si >= Si-8 + p[i]
2. 1 <= i <= 7 , 因为覆盖的范围可以到S24 ~ S(24-(8-i))这个区间里,所以要两段拼接起来:
前半段Si , 后半段S24 - S(16+i) , 即为Si >= p[i] + S16+i - S24 (不符合标准格式,所以枚举S24的所有取值)
3.前缀和数组需要满足: Si >= Si-1
4.前提是i时段的人数不能超过题目给出的i时段的人数:
Si-1 >= Si - num[i]
5.承接第二条,单独从不等式分离出来的S24自身也要连一条边:
S24 = c ====> S24 >= c , c >= S24;
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 30, M = 300;
int p[N]; //为题目中i时刻需要的人数
int num[N]; //为i时刻题目给出的收银员人数
int h[N],ne[M],e[M],w[M],idx;
queue<int> q;
bool st[N];
int dist[N];
int cnt[N];
int qi[N];
int 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){ //c表示的就是S24的值
memset(h,-1,sizeof h);
idx = 0;
add(0, 24, c), add(24, 0, -c); //注意单独分出来的S24
for(int i = 8;i <= 24;++i) add(i - 8,i,p[i]);
for(int i = 1;i <= 7;++i) add(16 + i,i,p[i] - c);
for(int i = 1;i <= 24;++i) add(i - 1,i,0);
for(int i = 1;i <= 24;++i) add(i,i - 1,-num[i]);
}
bool spfa(int c){ //求最长路,判断正环
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
memset(dist,-0x3f,sizeof dist);
build(c);
//差分约束从源点出发
q.push(0);
st[0] = true;
dist[0] = 0;
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];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= 25) return false;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return true;
}
int main(){
int t;
cin >> t;
while(t--){
for(int i = 1;i <= 24;++i){ //因为用前缀和所以从1开始计数
cin >> p[i];
}
cin >> n;
memset(num,0,sizeof num);
for(int i = 1;i <= n;++i){ //因为用前缀和所以从1开始计数
int mo;
cin >> mo; mo++;
num[mo]++;
}
//枚举一下S24的值
bool flag = true;
//(具有单调性,用二分优化这部分)
for(int i = 0;i <= 1000;++i){ //直到枚举到第一个合法的S24即是满足要求的下届的最大值
if(spfa(i)){
flag = false;
break;
}
}
if(!flag) printf("%d\n",dist[24]);
else puts("No Solution");
}
return 0;
}
二分优化
C++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 30, M = 300;
int p[N]; //为题目中i时刻需要的人数
int num[N]; //为i时刻题目给出的收银员人数
int h[N],ne[M],e[M],w[M],idx;
queue<int> q;
bool st[N];
int dist[N];
int cnt[N];
int qi[N];
int 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){ //c表示的就是S24的值
memset(h,-1,sizeof h);
idx = 0;
add(0, 24, c), add(24, 0, -c); //注意单独分出来的S24
for(int i = 8;i <= 24;++i) add(i - 8,i,p[i]);
for(int i = 1;i <= 7;++i) add(16 + i,i,p[i] - c);
for(int i = 1;i <= 24;++i) add(i - 1,i,0);
for(int i = 1;i <= 24;++i) add(i,i - 1,-num[i]);
}
bool spfa(int c){ //求最长路,判断正环
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
memset(dist,-0x3f,sizeof dist);
build(c);
//差分约束从源点出发
q.push(0);
st[0] = true;
dist[0] = 0;
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];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= 25) return false;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return true;
}
int main(){
int t;
cin >> t;
while(t--){
for(int i = 1;i <= 24;++i){ //因为用前缀和所以从1开始计数
cin >> p[i];
}
cin >> n;
memset(num,0,sizeof num);
for(int i = 1;i <= n;++i){ //因为用前缀和所以从1开始计数
int mo;
cin >> mo; mo++;
num[mo]++;
}
//二分枚举一下S24的值
int l = 0, r = n;
while(l < r){
int mid = l + r >> 1;
if(spfa(mid)) r = mid;
else l = mid + 1;
}
if(r == n) puts("No Solution");
else printf("%d\n",l);
}
return 0;
}
很清晰!Or2