A Huster

0%

差分约束-SPFA系统

Posted on Edited on Valine:

据说差分约束有很多种，但是我学过的只有SPFA求差分；

我们知道，例如 $A-B<=C$ ，那么这就是一个差分约束。

比如说，著名的三角形差分约束，这个大家都是知道的，什么两边之差小于第三边啦，等等等等。

所以说，我们学他干嘛（我们得出结论：学他没用，谢谢大家观看）

咳咳——说正事，我们来看一道例题：【luoguP1993】小K的农场：

题目描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：

  • 农场a比农场b至少多种植了c个单位的作物，
  • 农场a比农场b至多多种植了c个单位的作物，
  • 农场a与农场b种植的作物数一样多。

但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式：

第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。

接下来 m 行：

如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，接下来有 2 个整数 a,b，表示农场 a 种植的的数量和 b 一样多。

输出格式：

如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。

我们看一看题干，能够发现一些条件：

我们一个一个分析先分析第2个（为什么？等会就明白了）

题中让我们求得是否能够让条件成立，那么就用到我们的SPFA了，怎么用？

还记得SPFA那个更新条件吗

$dis[y]>dis[x]+edge[i].w$ ;

所以说，让我们反想一下，既然我们求得答案，那么我们肯定想

;

因为这样最后我们就可以求得答案了；

那么如果我们将它推论到差分系统呢，我们想让它成立，那么就要让他限制于一个条件，那么很容易就能懂C应该是 $edge[i].w$ ;

那么我们推一下, $A<=B+C -> A-B<=C$ 。这样我们建一个由B指向A的边，边权为C，那么我们再来看第一个条件就很容易懂了。

这个就直接说了, $B-A<=-C$ ，之后就和前面的一样了；

那么来看最后一个条件： $A=B$ 。这个应该是初中（应该不是的小学吧QWQ）数学的知识， $A>=B $&& $A<=B$ ，就可以实现这个条件的差分替换了;

那么再用上SPFA的judge负环的骚操作就可以了。

这样应该就能写出来这道题了——吗?

你会发现你从1点开始跑会有70分，（其实是水的），为什么呢？

这是因为图可能并不联通，那么你这样跑就会凉凉，那么我们可以建一个超级原点，这样就可以联通了，提交发现60分

！！！怎么还少了QAQ！！！

所以说上面的过程是水的呀，我们会T掉，因为BFS会一直在圈里跑，而圈子又太大，那么SPFA的诟病就出来了（关于SPFA，它死了）

SPFA还没有凉透，因为我们会出现负环，而题中就让我们判断负环，我们没法用其他算法啊！

那么就有了应运而生的 $SPFA-DFS$ 判负环版本，来看一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool SPFA(int x){
    vis[x]=1;//标记在搜索过程中 
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(dis[y]>dis[x]+edge[i].w){
            dis[y]=dis[x]+edge[i].w;
            if(vis[y]) return true;/*循环环出现，也就是负权值不停更新
             ，那么我们用这个机制就可以return了*/
            if(SPFA(y)) return true;
        }
    }
    vis[x]=0;//清除标记 
    return false;//条件成立 
}

这样就不会TLE了；

现在来看完整代码（其中有BFS的TLE代码）：

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 #include<bits/stdc++.h>
#define maxn 10007
using namespace std;
int n,m,head[maxn],cent,vis[maxn],dis[maxn],num[maxn];
struct node{
    int next,to,w;
}edge[maxn<<2];
queue<int >q;

void add(int u,int v,int w){
    edge[++cent]=(node){head[u],v,w};head[u]=cent;
}

//bool SPFA(int x){
//    vis[x]=1,num[x]++,dis[x]=0;
//    q.push(x);
//    while(!q.empty()){
//        int x=q.front();vis[x]=0;q.pop();
//        for(int i=head[x];i;i=edge[i].next){
//            int y=edge[i].to;
//            if(dis[y]>dis[x]+edge[i].w){
//                dis[y]=dis[x]+edge[i].w;
//                if(!vis[y]){
//                    q.push(y);
//                    num[y]++;
//                }
//                if(num[y]>=n){
//                    return true; 
//                }
//            }
//        }
//    }
//    return false;
//}

bool SPFA(int x){
    vis[x]=1;//标记在搜索过程中 
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(dis[y]>dis[x]+edge[i].w){
            dis[y]=dis[x]+edge[i].w;
            if(vis[y]) return true;/*循环环出现，也就是负权值不停更新
             ，那么我们用这个机制就可以return了*/
            if(SPFA(y)) return true;
        }
    }
    vis[x]=0;//清除标记 
    return false;//条件成立 
}

int main(){
//    freopen("cin.in","r",stdin);
//    freopen("cout.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,s,a,b,c;i<=m;i++){
        scanf("%d%d%d",&s,&a,&b);
        if(s==1){
            scanf("%d",&c);
            add(a,b,-c);
        }else if(s==2){
            scanf("%d",&c);
            add(b,a,c);
        }else if(s==3){
            add(a,b,0);
            add(b,a,0);
        }
    }
    for(int i=1;i<=n;i++) add(0,i,0);//超级源点 
    memset(dis,0x3f3f3f,sizeof(dis));
    dis[0]=0;//搜索初始化 
    if(SPFA(0)) printf("No");    
    else printf("Yes");
    return 0;
}

这道题就结束了，再送一道福利题[USACO05DEC]

好了，就这样了。

本站访问次数：