前置芝士: SPFA 判负环
对于差分约束系统, 就是来解决一系列类似下面的问题:
差分约束系统是一种特殊的 \(N\) 元一次不等式组, 它包含 \(N\) 个变量 \(X_1...X_n\) 以及 \(M\) 个约束条件. 每个约束条件都是由两个变量做差构成的.
我们要求的是, 一组解 \(X_1=a,X_2=b...\) 满足所有的约束条件.
对于每一个不等式, 我们都可以变形成 \(X_i-X_j<=C\) 的形式, 而移项之后, 我们会发现它与最短路算法的松弛操作很相似. 也就是说, 我们可以从 \(j\) 向 \(i\) 连一条边长为 \(C\) 的有向边, 跑最短路.
对于形如 \(X_i-X_j>=C\) 的形式, 两边乘以 \(-1\) 即可.
对于建出来的图, 如果存在负环则无解, 否则 \(X_i=dis[i]\) 就是一组解.
对于判负环, 那显然就要用到我们的 \(Spfa\) 了.
例 1:\(luogu\) \(P1993\)
显然是一道差分约束的裸题. 这是最直接的模型, 直接跑即可.
代码:
- #include<cstdio>
- #include<iostream>
- #include<queue>
- #include<cstring>
- #define MAXN 10001<<1
- using namespace std;
- inline int read(){
- int s=0,w=1;
- char ch=getchar();
- while(ch<'0'||ch>'9'){
- if(ch=='-')w=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9'){
- s=(s<<1)+(s<<3)+(ch^48);
- ch=getchar();
- }
- return s*w;
- }
- struct edge{
- int nxt,to,dis;
- }e[MAXN<<1];
- int head[MAXN<<1],dis[MAXN],opt,a,b,c;
- int vis[MAXN],n,m,tot,cnt[MAXN];
- queue<int>q;
- inline void add(int x,int y,int w){
- e[++tot].to=y;
- e[tot].nxt=head[x];
- e[tot].dis=w;
- head[x]=tot;
- }
- bool Spfa(int s){
- memset(dis,0x3f,sizeof(dis));
- dis[s]=0;q.push(s);vis[s]=1;
- while(!q.empty()){
- int k=q.front();
- q.pop();vis[k]=0;
- cnt[k]++;
- if(cnt[k]>=n)return 0;
- for(int i=head[k];i;i=e[i].nxt){
- int j=e[i].to;
- if(dis[j]>dis[k]+e[i].dis){
- dis[j]=dis[k]+e[i].dis;
- if(!vis[j])vis[j]=1,q.push(j);
- }
- }
- }
- return 1;
- }
- bool spfa(int s){
- vis[s]=1;
- for(int i=head[s];i;i=e[i].nxt){
- int j=e[i].to;
- if(dis[j]<dis[s]+e[i].dis){
- dis[j]=dis[s]+e[i].dis;
- if(vis[j])return 0;
- if(!spfa(j))return 0;
- }
- }
- vis[s]=0;
- return 1;
- }
- int main(){
- n=read(),m=read();
- for(int i=1;i<=m;++i){
- opt=read(),a=read(),b=read();
- if(opt==1){
- c=read();//Xi-Xj>=c
- add(b,a,c);
- }
- else if(opt==2){
- c=read();
- add(a,b,-c);
- }
- else if(opt==3){
- add(a,b,0);
- add(b,a,0);
- }
- }
- for(int i=1;i<=n;++i)add(0,i,0),dis[i]=-0x3f;
- if(!spfa(0))printf("No\n");
- else printf("Yes\n");
- return 0;
- }
练习题:
- \(luogu\) \(P4878\)
- \(luogu\) \(P3275\)
来源: http://www.bubuko.com/infodetail-3156886.html