差分约束算法
约束条件：$x_i-x_j\leqslant c_k$
可以变成：$x_i\leqslant c_k+x_j$
我们将所有条件变成只取等号的形式：$x_i=c_k+x_j$
我们将所有的条件之间连上边，然后跑最短路，这样可以保证所有的约束条件一定都符合要求。
将所有点和源点连边（防止有点在求最短路时落掉）。
但是，会出现负环的情况，即没有解的情况，我们可以考虑如果一组有解，那么一个点最多被使用 $n-1$ 次（自己不连自己），加上源点，就是 $n$ 次，而负环会一直遍历下去，所以我们直接判断点遍历的次数有没有超过 $n$，即可。若超过直接返回无解。
题解
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
long long r_r(){
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e4+10;
struct po{
int v,l,n_t;
}p_p[o_o];
int h_d[o_o],t_t[o_o],v_v[o_o],b_b[o_o],x_p,n,m;
void a_d(int u,int v,int w){
p_p[++x_p].v=v;
p_p[x_p].l=w;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
queue<int> q;
bool s_f(int s){
memset(v_v,63,sizeof(v_v));//初始化各个节点价值
v_v[s]=0,b_b[s]=1;//初始化源点信息
q.push(s);//加入源点
while(!q.empty()){
int k=q.front();
q.pop();
b_b[k]=0;//初始化节点价值
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(v_v[v]>v_v[k]+p_p[i].l){//找到价值更小的解法
v_v[v]=v_v[k]+p_p[i].l;//更新
if(!b_b[v]){//目标节点还未遍历过
b_b[v]=1;//标记
t_t[v]++;//更新使用节点次数
if(t_t[v]>n)return 0;//出现负环
q.push(v);//加入遍历队伍
}
}
}
}
return 1;
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;i++)a_d(0,i,0);//所有未知量和源点连边
for(int i=1;i<=m;i++){
int v=r_r(),u=r_r(),w=r_r();
a_d(u,v,w);//存边
}
if(!s_f(0))puts("NO");//不存在路径
else for(int i=1;i<=n;i++)printf("%d ",v_v[i]);//输出结果
return 0;
}
糖果
我们将边权定义为当前点到下一个点如果合法的话，至少比当前点的糖果数多加几个糖果，所没回我们找到的都是至少合法。
那么我们遍历的就不能是最短路，以为如果是最短路更新边的话，一定会出现不合法情况。
本题连最长路，如果出现正环，说明不合法。
- 如果 $X=1$， 表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
将 $(A,B)=0,(B,A)=0$ 连边，保证 $A,B$ 值相等。
- 如果 $X=2$， 表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
将 $(A,B)=1$ 连边，保证表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果 $1$ 个。
- 如果 $X=3$， 表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
将 $(B,A)=0$ 连边，保证表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果。
- 如果 $X=4$， 表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
将 $(B,A)=1$ 连边，保证表示第 $B$ 个小朋友分到的糖果必须少于第 $A$ 个小朋友分到的糖果 $1$ 个。
- 如果 $X=5$， 表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；
将 $(A,B)=0$ 连边，保证表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
long long r_r(){
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e6+10;
struct po{
int v;
int n_t;
int l;
}p_p[o_o];
int n,k,h_d[o_o],x_p,v_v[o_o],t_t[o_o];
bool b_b[o_o];
queue<int>q;
void a_d(int u,int v,int l){//加边
p_p[++x_p].v=v;
p_p[x_p].n_t=h_d[u];
p_p[x_p].l=l;
h_d[u]=x_p;
}
int main(){
n=r_r(),k=r_r();
while(k--){
int op=r_r(),u=r_r(),v=r_r();
if(op==1)a_d(u,v,0),a_d(v,u,0);//建来回边保证值得相同
else if(op==2){
if(u==v){
puts("-1");//自己不能小于自己
return 0;
}
a_d(u,v,1);//A 连向 B，且 B 一定比 A 至少大 1
}
else if(op==3)a_d(v,u,0);//A 不小于 B
else if(op==4){
if(v==u){
puts("-1");//自己不能小于自己
return 0;
}
a_d(v,u,1);//B 连向 A，且 A 一定比 B 至少大 1
}
else if(op==5)a_d(u,v,0);//B 不小于 A
}
for(int i=n;i>=1;i--)a_d(0,i,1);//与源点建边
b_b[0]=1,q.push(0);//从源点开始跑
while(!q.empty()){
int k=q.front();
q.pop();
b_b[k]=0;
if(t_t[k]==n-1){//存在正环
puts("-1");
return 0;
}
t_t[k]++;//使用次数累计
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(v_v[v]<v_v[k]+p_p[i].l){//更长
v_v[v]=v_v[k]+p_p[i].l;//更新结果
if(!b_b[v]){//没使用过
b_b[v]=1;//标记
q.push(v);//遍历
}
}
}
}
long long a_s=0;
for(int i=1;i<=n;i++)a_s+=v_v[i];//统计答案
printf("%lld ",a_s);//输出结果
return 0;
}
