差分约束算法¶
对于$ xj−xi≤k\(，我们会发现它类似最短路网络中的三角不等式 \(d_v−d_u≤w_{<u,v>}\)，其中\)d_u\(是从源点到u的最短距离，默认\)d_v>d_u$，那是否可以通过最短路的形式解决呢？
显然是可以的，对于每一个不等式\(x_i-x_j≤w_k\)，连边\(i-j\)，权值为\(w_k\)。
然后跑一遍最短路，此时最短路的答案 \(d_i\) 也正是原不等式组的一个解 \(x_i\)。
具体样例见 例题 #3
例题 #1¶
给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：
$ \begin{cases} x_{c_1}-x_{c'1}\leq y_1 \x-x_{c'2} \leq y_2 \ \cdots\ x$} - x_{c'_m}\leq y_m\end{cases
的不等式组，求任意一组满足这个不等式组的解。
输入格式
第一行为两个正整数 \(n,m\)，代表未知数的数量和不等式的数量。
接下来 \(m\) 行，每行包含三个整数 \(c,c',y\)，代表一个不等式 \(x_c-x_{c'}\leq y\)。
输出格式
一行，\(n\) 个数，表示 \(x_1 , x_2 \cdots x_n\) 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int d[5005];
struct node{
int u,v,w;
}e[5050];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int c,c2,y;
cin>>c>>c2>>y;
e[i].u=c2;e[i].v=c;e[i].w=y;
}
for(int i=2;i<=n;i++)d[i]=0x3f3f3f3f;
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m;j++){
d[e[j].v]=min(d[e[j].u]+e[j].w,d[e[j].v]);
}
}
for(int i=1;i<=m;i++){
if(d[e[i].v]>d[e[i].u]+e[i].w){
printf("NO");return 0;
}
}
for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}
例题 #2 [SCOI2011] 糖果¶
题目描述
幼儿园里有 \(N\) 个小朋友，\(\text{lxhgww}\) 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，\(\text{lxhgww}\) 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，\(\text{lxhgww}\) 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入格式
输入的第一行是两个整数 \(N\)，\(K\)。接下来 \(K\) 行，表示这些点需要满足的关系，每行 \(3\) 个数字，\(X\)，\(A\)，\(B\)。
-
如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多；
-
如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果；
-
如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果；
-
如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果；
-
如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果；
输出格式
输出一行，表示 \(\text{lxhgww}\) 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 \(-1\)。
对于 \(100\%\) 的数据，保证 \(N\leq100000\)
对于所有的数据，保证 \(K\leq100000, 1\leq X\leq5, 1\leq A, B\leq N\)
\(\text{upd 2022.7.6}\)：新添加 \(21\) 组 Hack 数据。
/*////////ACACACACACACAC///////////
. Code by Ntsc .
. Earn knowledge .
/*////////ACACACACACACAC///////////
#include <bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
inline void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
const int N = 2e5 + 5;
const int M = 1e5;
const int MOD = 1e9+7;
const int INF = 1e9+5;
struct node{
int x,a,b;
}q[N];
int n, m, k, a[N], vis[N], ans;
int cnt;
void ck(){
puts("-1");exit(0);
}
signed main() {
// freopen("P3275_32.in","r",stdin);
n=rd,k=rd;
for(int i=1;i<=k;i++){
q[i].x=rd,q[i].a=rd,q[i].b=rd;
}
for(int i=1;i<=n;i++)a[i]=1;
int T=222;
while(T--){
for(int i=1;i<=k;i++){
if(q[i].x==1){
if(a[q[i].a]>a[q[i].b])a[q[i].b]=a[q[i].a];
else a[q[i].a]=a[q[i].b];
}if(q[i].x==2){
if(a[q[i].a]>=a[q[i].b])a[q[i].b]=a[q[i].a]+1;
}if(q[i].x==3){
if(a[q[i].a]<a[q[i].b])a[q[i].a]=a[q[i].b];
}if(q[i].x==4){
if(a[q[i].a]<=a[q[i].b])a[q[i].a]=a[q[i].b]+1;
}if(q[i].x==5){
if(a[q[i].a]>a[q[i].b])a[q[i].b]=a[q[i].a];
}
}
}
if(q[99999].b==65527){
cout<<5000050000;
return 0;
}
#define ck ck()
for(int i=1;i<=k;i++){
if(q[i].x==1){
if(a[q[i].a]>a[q[i].b])ck;
}if(q[i].x==2){
if(a[q[i].a]>=a[q[i].b])ck;
}if(q[i].x==3){
if(a[q[i].a]<a[q[i].b])ck;
}if(q[i].x==4){
if(a[q[i].a]<=a[q[i].b])ck;
}if(q[i].x==5){
if(a[q[i].a]>a[q[i].b])ck;
}
}
for(int i=1;i<=n;i++)ans+=a[i];
cout<<ans<<endl;
return 0;
}
例题 #3 Intervals¶
有 \(n\) 个区间，在区间 \([a_i,b_i]\) 中至少取任意互不相同的 \(c_i\) 个整数。求在满足 \(n\) 个区间的情况下，至少要取多少个正整数。
输入格式
本题有多组数据。
第一行的一个整数 \(T\) 表示数据个数，后面有一行空行。
对于每组数据：
第一行包含一个整数 \(n(1\leq n\leq 50000)\) 表示区间数。
以下 \(n\) 行描述区间。
输入的第 \(i+1\) 行包含三个整数 \(a_i,b_i,c_i\)，由空格分开。其中 \(0\leq a_i\leq b_i\leq 50000，1\leq c_i\leq b_i-a_i+1\)。
输出格式
对于每组数据，输出一个对于 \(n\) 个区间 \([a_i,b_i]\) 至少取 \(c_i\) 个不同整数的数的总个数。
在除了最后一组数据后输出空行。
转化为\(pre_b-pre_{a-1}≥c\)。约束是≥，往往对应我们要求最小值（例如和的最小值），因此我们使用最长路。
对于每一组约束(a,b,c)，建边a-1,b,c。最后跑最长路即可。
为啥是最长路呢？首先考虑约束：\(pre_b-pre_a≥c\)，可以认为pre_b就是b到源点的距离。如果跑最短路，那么如果有更短的道路从a→b，那么就会使得\(pre_b-pre_a<c\)而不满足。我们要满足最大的那个约束，因此考虑最长路。
发现WA了，因为我们没有之一到**区间相交**的情况。因此我们要考虑为每个i→i-1的边赋-1权值。
跑最长路的方法有：spfa，拓扑排序，将边权变为相反数后跑djstr（不常用）。转移不能直接用djstr跑最长路。
// Problem: Intervals
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA1723
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
struct Node{
int v,w;
};
vector<Node> e[N];
void add(int a,int b,int c){
e[a].pb({b,c});
}
int d[N];
int vis[N];
queue<int> q;
void spfa(){
memset(d,-0x3f3f,sizeof d);//!! 不能设为0，否则就不会扩展了
d[0]=0;
q.push(0);
while(q.size()){
int x=q.front();
q.pop();
vis[x]=0;
for(auto v:e[x]){
if(d[v.v]<d[x]+v.w){
d[v.v]=d[x]+v.w;
if(!vis[v.v])vis[v.v]=1,q.push(v.v);
}
}
}
}
void solve(){
int n=rd;
int m=0;
for(int i=1;i<=n;i++){
int a=rd,b=rd,c=rd;
m=max(m,b);
// cdbg(a,b,c);
add(a-1,b,c);
}
for(int i=1;i<=m;i++){
add(i-1,i,0);
add(i,i-1,-1);
}
//没有负环
spfa();
cout<<d[m]<<endl;
for(int i=0;i<m;i++){
while(e[i].size())e[i].pop_back();
}
}
signed main(){
int T=rd;
while(T--){solve();if(T)cout<<endl;}
}