图论扩展

1.差分约束

中心思想：利用最短路算法解决一系列约束的可行性

转化思路：差分约束的题目一般会给你类似于$a \leq b+i, b \gt c-j, a=d(i,j均为常数)$诸如此类的约束条件，我们会把它看成最短路的形式

举个例子，我们已知$u \gt v+w(w为常数)$，思考一下在最短路算法中我们使用什么来进行松弛证明路径最短化

三角不等式对吧，假设$a->$b有一条权值为$c$的道路，则$dis[b] \leq dis[a]+w->dis[b]-dis[a] \leq w$，

同理，我们把式子$u \gt v+w$变形为$v-u \lt w$，这不狱盐顶针就是从$u$到$v$连了一条边权为$w$的有向边吗

因为这些约束全部满足代表它有解，无解就代表$v-u \gt w$，也就是存在负环的时候无解，而每个点的最短路其实也就对应了一组解

但是如果存在孤立点(跟其它任一点无连边)且各连通块之间的关系是什么呢，可等也可不等对吧

解决方法很简单，给定一个超级原点，每个点都向它连接双向的权值为0的边，也就满足了“可等也可不等”这个条件而且不会增加负环

并且这个边其实都不用连，分析一下，其实就是每个点的初始$min\_dis[i]$都成了超级原点走一条0权边就等于0就可以了

---

2.传递闭包

中心思想：利用二进制优化解决传递性条件类问题

优化过程：对于最基础的传递闭包，不难顶针看出使用$O(n^3)$的$Floyd$就可以得到任意两点间关系

vector< vector< int > > floyd;
for( int k=1;k<=n;k++ ）
    for( int i=1;i<=n;i++ )
        for( int j=1;j<=n;j++ )
            floyd[i][j]|=floyd[i][k]&floyd[k][j];

但$O(n^3)$的时间复杂度可真谓是震地看了流泪，古月看了心碎

问题出在哪里呢？因为要求最短路，所以我们要进行$n$轮的松弛操作，但在传递闭包中，我们不关心路径长度，只关心连通性

所以我们没必要进行中间点枚举，如果$a$能到$b$，则$a$也能到达$b$能到的点就够判断连通性了，时间复杂度也优化到了$O(n^2)$

//二进制便于连通性的修改
bitset< N > floyd[N];
for( int i=1;i<=n;i++ )
    for( int j=1;j<=n;j++ )
        //如果j能到i，则j也能到i能到的点
        if( floyd[j][i] ) floyd[j]|=floyd[i];

3.分层图

应用场景：分层图本身并非一种算法，而是一种数据结构或图的表示形式，用于描述具有层次关系的数据，这里我们常用其解决一类特殊的最短路问题

解决思路：这类问题一般会在本身的图的基础上增加部分信息，例如"有$k$次机会减少边权，每个点可以以$w$的花费修改某个参数"等等

这些问题不好在本身的图上面处理，因为你不知道现在使用这些条件还是待会使用会得到更优解

但我们可以发现，在使用条件后，我们的图不会改变，即点权，边权与连通性都不会改变，我们可以利用这个来解决问题

我们可以优先建出多个图，代表了不同的使用后状态，就可以把所有条件的使用计算在内

在不同的图之间，用单向连边来处理增加的信息，代表可以从这个点使用增加信息来转移到下一个状态上

这样我们建图完后就会得到一个有很多层(状态)，层与层之间又有连边的张图，在这张图上跑最短路就能得到最终答案

而且我们不一定要把图建出来，可以用码量换空间，跑最短路时多记录几维的信息，然后判断并转移即可