djwj233 的博客

djwj233 的博客

负环与差分约束系统 学习笔记

posted on 2021-10-07 14:25:10 | under 笔记 |

负环

在一张带权图 $G$ 中,若有一个环满足环上边权之和为负,则称这个环为负环

可以发现,带负环的图不存在最短路,因为可以构造一条路径不停地绕着这个环走使总长度为 $-\infty$。

一般可以用 Bellman-Ford 或 SPFA 判负环,其中 SPFA 在随机图上表现出色,但二者的最劣时间复杂度都是 $\Theta(nm)$ 的。

我们发现,应用 Bellman-Ford 算法时,负环不存在时 $1$ 号点到任意点的最短路包含的边数不超过 $n-1$(否则肯定会重复经过某个点)。

因此可以在做完 $n-1$ 轮松弛后再遍历一遍所有边,若依然能松弛则表示有负环存在。

核心代码:

int n,m,dis[N]; bool vis[N];
struct edge {
    int u,v,w;
} e[M]; int tot;

void solve()
{
    cin>>n>>m; tot=0;
    fo(i,1,m) {
        tot++, scanf("%d%d%d",&e[tot].u,&e[tot].v,&e[tot].w);
        if(e[tot].w>=0) {
            tot++, e[tot].u=e[tot-1].v;
            e[tot].v=e[tot-1].u, e[tot].w=e[tot-1].w;
        }
    }
    memset(dis,0x3f,sizeof(dis)), memset(vis,0,sizeof(vis));
    dis[1]=0, vis[1]=true;
    fo(i,2,n) {
        bool ok=true;
        fo(j,1,tot) if(dis[e[j].v]>dis[e[j].u]+e[j].w) {
            ok=false, dis[e[j].v]=dis[e[j].u]+e[j].w;
            if(vis[e[j].u]) vis[e[j].v]=true; 
        }
        if(ok) break;
    }
    fo(j,1,tot) if(vis[e[j].u]&&vis[e[j].v]&&dis[e[j].v]>dis[e[j].u]+e[j].w)
        return puts("YES"), void();
    puts("NO");
}

对应到 SPFA 算法上,则需要判断一个点入队次数是否 $\geq n$,若 $\geq n$ 则表示有负环存在。

还有一种方法是记录每个点的最短路长度,这种方法一般效率更高。

差分约束系统

概念

差分约束系统(system of difference constraints)是一种特殊的 $n$ 元一次不等式组,里面的每一个条件都是$$ x_i-x_j \le c_k $$ 的形式,也就是两变量之差不大于某数。(若要求不小于可以把 $i,j$ 调换顺序)

问题要求给出一组合法解,或者判断它无解。

模型的转换

可以移项得到:$$ x_i\le x_j+c_k $$ 这正是最短路中的三角形不等式的形式:$$ \forall (u,v,w)\in E,\ dis_v\le dis_u+w $$ 那么我们可以尝试建图,对每个不等式连边 $(j,i,c_k)$,然后考虑跑最短路。

但是这个图不一定是一个流图,我们难以找出一个源点跑单源最短路,于是我们可以新建一个虚拟源点 $0$,对每个 $i\in[1,n]$ 连边 $(0,i,0)$。

现在我们以 $0$ 号点为源点跑一个单源最短路,跑出来每个点的最短路 $dis_i$ 一定是一组合法的解。

那么无解的情况呢?我们发现,差分约束系统无解当且仅当建出的图中不存在最短路,也即图中有负环。

这样我们就能以 $\mathcal O(n+m)$ 的时间解决这一问题了。

差分约束系统有一个平凡的性质:

若 $\{x_1,x_2,\cdots,x_n\}$ 是差分约束系统的一组合法解,则 $\forall \Delta\in\mathbb R$,$\{x_1+\Delta,x_2+\Delta,\cdots,x_n+\Delta\}$ 也是一组合法解。

这个结论是显然的。若 $x_i$ 中有负数,使用中常取 $\Delta=-\min{x_i}$,可构造出一组非负解。

这里使用 SPFA 算法求最短路。

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

const int N=5010, M=20010;

int n,m;

int head[N], Next[M], ver[M], edge[M], tot;
void add_edge(int x,int y,int z) {
    ver[++tot]=y, edge[tot]=z;
    Next[tot]=head[x], head[x]=tot;
}

int dis[N], cnt[N]; bool vis[N];
queue<int> q;

int main()
{
    cin>>n>>m;
    fo(i,1,m) {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        add_edge(y,x,z);
    }
    fo(i,1,n) add_edge(0,i,0);

    memset(dis,0x3f,sizeof(dis));
    dis[0]=0, vis[0]=true, q.push(0);
    while(q.size())
    {
        int x=q.front(); q.pop();
        vis[x]=false;
        for(int i=head[x]; i; i=Next[i]) {
            int y=ver[i];
            if(dis[y]>dis[x]+edge[i]) {
                dis[y]=dis[x]+edge[i];
                cnt[y]=cnt[x]+1;
                if(cnt[y]>=n+1) return puts("NO"),0;
                if(!vis[y]) vis[y]=true, q.push(y);
            }
        }
    }
    fo(i,1,n) printf("%d ",dis[i]);

    return 0;
}

注意因为实际上有 $n+1$ 个点,所以里面判负环需要写成 $\geq n+1$。

还有注意存边的数组不要开小!!!

常见建模思路

主要难在建模......

而且有些差分约束的题目还可以用贪心做,因此大多数差分约束的题目第一眼看是贪心(

总之就是看着十分难搞的二元约束性问题都可以考虑差分约束,最主要的点还是二元吧。

Trick 1 - 等号化为不等号

例题:P4578 [FJOI2018]所罗门王的宝藏

我们设 $row_i$ 为第 $i$ 行的转动结果,$col_i$ 为第 $i$ 列的转动结果。那么对于每个限制 $(x,y,c)$ 有:$$ row_i+col_i=c $$ 好像不太好搞?实际上,原式就是:$$ row_i-(-col_i)=c $$ (重点)既然有差分约束的影子了,那么就可以把这个等号拆成两个约束:$$ \begin{cases} row_i-(-col_i)\le c \\ (-col_i)-row_i\le -c \end{cases} $$ 也就是说等号相当于连反向、反权边

Code

Trick 2 - 前缀和形式

例题:P2294 [HNOI2005]狡猾的商人

这个前缀和的提示还算比较明显的,有些题目可能更为隐晦。

一般题目给出的约束是区间上一整段 至少/至多 的价值,就可以考虑前缀和形式。

设 $S_i=\sum_{k=1}^i a_i$,那么每个限制条件 $(s,t,v)$ 可被写作:$$ S_t-S_{s-1}\le v $$

$$ S_{s-1}-S_t\le -v $$

然后就可以搞了。注意这里 $s-1$ 能取到 $0$,因此可以把源点设成 $n+1$。

Code

Trick 3 - 结合最短路和最长路

例题:P2474 [SCOI2008]天平(难)

考虑到里面要求必定成立,因此我们考虑跑出每个组差的上界和下界。

我们注意到对于任意 $x,y$,由于 $a_x,a_y\in[1,3]$,因此 $-2\le a_x-a_y\le2$,这便是所有字符需要满足的条件。

+:$a_x>a_y\Rightarrow a_x-a_y\geq 1$,有 $a_x\geq a_y+1$。

-:$a_x<a_y\Rightarrow a_x-a_y\le -1$,有 $a_x\leq a_y-1$。

=:$a_x=a_y\Rightarrow a_x\le a_y\land a_y\le a_x$。

?:$a_x\geq a_y-2\land a_x\le a_y+2$。

因此我们注意到对同一个 $a_x$,既有 $\le$ 的限制条件,又有 $\ge$ 的限制条件

这里如果简单地取负数来把不等号反向,会多出来一个变量 $-a_x$,而它与 $a_x$ 是绑定死的,难以作为一个新变量。

这时我们可以考虑同时求最短路、最长路来把问题转化成类似于差分约束的形式。

建图部分:

fo(i,1,n) fo(j,1,n) dis0[i][j]=dis1[i][j]=114514;
   fo(i,1,n) {
    scanf("%s",s+1);
    fo(j,1,n) {
        if(s[j]=='+') {
            dis0[i][j]=1, dis1[i][j]=2, dis0[j][i]=-2, dis1[j][i]=-1;
        } else if(s[j]=='-') {
            dis0[i][j]=-2, dis1[i][j]=-1, dis0[j][i]=1, dis1[j][i]=2;
        } else if(s[j]=='=') {
            dis0[i][j]=dis1[i][j]=dis0[j][i]=dis1[j][i]=0;
        } else if(dis0[j][i]==114514) {
            dis0[j][i]=-2, dis1[j][i]=2;
        }
    }
}

由于要求出每个点对的差值,因此跑一个 Floyd 求出最短路和最长路,暴力枚举统计答案。

(这里的 $\texttt{dis0[i][j]}$ 表示 $x_i-x_j$ 的最小值, $\texttt{dis1[i][j]}$ 表示 $x_i-x_j$ 的最大值)

注意这里只考虑 $\texttt{dis0[A][i],dis1[j][B]}$ 是不行的,因为一边算出的信息不一定全。

fo(i,1,n) if(i!=A&&i!=B) fo(j,i+1,n) if(j!=A&&j!=B) {
    if( dis0[A][i]>dis1[j][B] || dis0[A][j]>dis1[i][B] ) cnt1++;
    else if( (dis0[A][i]==dis1[j][B]&&dis1[A][i]==dis0[j][B]) ||
        (dis0[A][j]==dis1[i][B]&&dis1[A][j]==dis0[i][B]) )
        cnt2++;
    else if( dis1[A][i]<dis0[j][B] || dis1[A][j]<dis0[i][B] )
        cnt3++;
}

Code

总结:用最短路径求差分方程组的最大解,用最长路径求差分方程组的最小解。

Trick 4 - 用 Tarjan 代替 Bellman-Ford/SPFA

这个东西真的很难想到(

例题:P3275 [SCOI2011]糖果

一眼差分约束,然后发现 $n$ 是 $10^5$ 级别的,很慌,可能会卡 SPFA。

注意到这里的差值只有 $1$,因此可以考虑先用 Tarjan 缩点然后在 DAG 上 DP。

具体看代码。Code

Trick 5 - 取 $\log$ 来化乘为加

显然先上一个二分答案,二分完自然想到从反面(没有任何人女装)的情况入手。

列出不等式组跑最短路,若无解则说明有人女装,否则无人女装。

但是,列出的不等式是这样的:$$ d_u\geq kd_v $$ 这个不等式含有倍数

怎么处理?我们发现可以通过 $\log$ 使运算降级,因此:$$ \ln d_u\geq\ln d_v+\ln k $$ 这样就可以了。Code


由于做法实在多变,就不放了qwq