来补一下自己很久以前那个很蒟蒻很蒟蒻的自己没有学懂的知识
差分约束，说白了就是利用我们在求最短路的一个\(relax\)操作时的判断的原理
\[dis[v]>dis[u]+disj(u,v)
\]
\]
然后题目中一般会给你一堆不等关系，我们就可以将他们转化成一个点一个点之间的约束关系
然后，这种东西就可以做啦
然后再来说一下这道题目
题目要求，对于给定的\(A,B,C\),使得
\[B-A<=C
\]
\]
然后我们发现，这不就是一道裸题吗
于是就可以愉快的码代码了
然后，再提醒一句，由于本题数据过于毒瘤，再加上\(NOI2018\)归程一题的*现场，建议各位不要使用\(SPFA\),毕竟人家已经死了
贴代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct cc{
int to,w,nex;
}e[400010];
int head[200010],cnt;
int d[200010];
void add(int a,int b,int c)
{
++cnt;
e[cnt].to=b;
e[cnt].w=c;
e[cnt].nex=head[a];
head[a]=cnt;
}
struct node{
int u,d;
bool operator<(const node &a)const{
return a.d<d;
}
};
priority_queue<node> q;
void DJ(int s)
{
memset(d,0x3f,sizeof d);
d[s]=0;
q.push((node){s,0});
while(!q.empty())
{
node fir=q.top();
q.pop();
if(d[fir.u]!=fir.d) continue;
for(int i=head[fir.u];i;i=e[i].nex)
{
int v=e[i].to;
if(d[v]>d[fir.u]+e[i].w)
{
d[v]=d[fir.u]+e[i].w;
q.push((node){v,d[v]});
}
}
}
}
int main()
{
int n,m,a,b,c;
while(scanf("%d%d",&n,&m)==2)
{
memset(head,0,sizeof head);
cnt=0;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&a,&b,&c),add(a,b,c);
DJ(1);
printf("%d\n",d[n]);
}
return 0;
}
然后又碰到本题的升级版
就是一共有五种不同的约束关系
所以要每一种每一种分开处理，将其化成我们松弛操作时的那个样子，然后就可以愉快的求解了
本题还有一个限制条件，每个孩子都必须要有糖果
这个很简单，就是建立一个超级源，与每个点的距离都为一就行了
但是，个人认为，本题你就只能硬着头皮使用\(SPFA\)了
还有，本题是有可能出现矛盾的情况的，所以需要在SPFA时判断负环
然后，就贴代码吧
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct cc{
int to,w,nex;
}e[400010];
int head[200010],cnt;
int d[200010];
void add(int a,int b,int c)
{
++cnt;
e[cnt].to=b;
e[cnt].w=c;
e[cnt].nex=head[a];
head[a]=cnt;
}
int n,m,a,b,c;
bool vis[200010];
int tot[200010];
queue<int> q;
void DJ(int s)
{
d[0]=0;
vis[0]=1;
q.push(s);
while(!q.empty())
{
int fir=q.front();
q.pop();
vis[fir]=0;
if(tot[fir]==n-1)
{
printf("-1\n");
exit(0);
}
++tot[fir];
for(int i=head[fir];~i;i=e[i].nex)
{
int v=e[i].to;
if(d[v]<d[fir]+e[i].w)
{
d[v]=d[fir]+e[i].w;
if(!vis[v])
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof head);
cnt=0;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&c,&a,&b);
if(c==1) add(a,b,0),add(b,a,0);
else if(c==2)
{
if(a==b)
{
printf("-1\n");
return 0;
}
else add(a,b,1);
}
else if(c==3) add(b,a,0);
else if(c==4)
{
if(a==b)
{
printf("-1\n");
return 0;
}
else add(b,a,1);
}
else add(a,b,0);
}
for(int i=n;i>=1;--i)
add(0,i,1);//超级源
DJ(0);
long long ans=0;
for(int i=1;i<=n;++i)
ans+=d[i];
printf("%lld",ans);
return 0;
}