[POI2012]FES-Festival

Link
看到题目首先肯定想到差分约束，当然这也是一个差分约束的题。
题目比较难想的地方在于建图，设 $Dist[i][j]$ 表示 $max\{A_i - A_j\}$ ，也就是 $A_i$ 最多能比 $A_j$ 大多少。那么根据题意我们知道对于第一种情况，应该是

$Dist[X][Y] = 1,~Dist[Y][X] = - 1$

然后对于第二种情况，题目对数量上并没有限制，限制的只是大小关系，然而我们转化一下依然能知道 $A_Y - A_X \geq 0$ ，对此我们选择从 $Y$ 向 $X$ 连一条边权为零的单项边，然后 $Dist[Y][X] = 0$ ，对于这种情况我们连边的目的不是为了限制数值，而是为了限制关系，大小关系。
由于限制条件可以叠加，于是对于每一个建边都要取 $min$ 。
然后首先要考虑的肯定是合法问题。稍加分析我们可以知道图如果存在非零环，肯定是不合法的，于是我们考虑判断非零环。
一般来说判负环就是简单地跑一遍 $Spfa$ 然后记录每一个点入队的次数就可以解决。但是这个题有一点问题。就是这个图并不一定是联通的。所以不论以哪一个节点作为起点都是不能保证的。因此舍弃 $Spfa$ ，观察数据发现 $N \leq 600$ 非常的小，完全可以考虑 $Floyed$ ，使用弗洛伊德的判断负环的方式就是看有没有 $Dist[i][i] != 0$ ，然后弗洛伊德怎么解决问题了呢？
因为图并不是联通的，但是只要每一个强连通分量合法就可以了，于是我们考虑 $Tarjan$ 缩点，然后对于每一个强联通分量分别求解。
在三重循环的过程中判断 $i,j,k$ 是不是都属于一个强连通分量，然后就可以有一个小小的优化。
缩完点之后发现剩下的就是连接每一个联通块的零权边，对答案并没有影响，只会影响关系，并且我们设的 $Dist[i][j]$ 表示的是 $i,j$ 的最大差值，于是就可以寻找每一个强联通分量里面的最大值。并且每一个强联通分量在数值上没有关系，因此将答案直接累加即可，最后输出答案加上强连通分量的数量。

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

#define RE register

using namespace std ;

typedef long long LL ;
const int MAXN = 610 ;
const int MAXM = 100010 ;
const int Inf = 1000000000 ;

int N, M1, M2, D[MAXN], H[MAXN], Tot ;
int Low[MAXN], Dfn[MAXN], B[MAXN] ;
int S[MAXN], Top, Ken, Cnt, Ans ; 
bool Insta[MAXN], Inq[MAXN], V[MAXN] ;
int Num[MAXN], Max, Dist[MAXN][MAXN] ;
queue <int> Q ;

struct Node {
    int F, T, L, Next ;
}   E[MAXM << 1] ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline void Add(int F, int T, int L) {
    E[++ Tot].F  = F, E[Tot].T = T ;
    E[Tot].L = L ; E[Tot].Next = H[F] ; 
    H[F] = Tot ;
}

inline void Tarjan(int Now) {
    Dfn[Now] = Low[Now] = ++ Ken ;
    S[++ Top] = Now ; Insta[Now] = 1 ;
    for (RE int i = H[Now] ; i ; i = E[i].Next) 
        if (! Dfn[E[i].T]) {
            Tarjan(E[i].T) ; Low[Now] = min(Low[E[i].T], Low[Now]) ;
        } else if (Insta[E[i].T]) Low[Now] = min(Dfn[E[i].T], Low[Now]) ;
    if (Dfn[Now] == Low[Now]) {
        Cnt ++ ; int Pass ;
        do { Pass = S[Top --] ; B[Pass] = Cnt ; Insta[Pass] = false ;
        }   while (Pass != Now) ;
    }
}

int main() {
    N = Read(), M1 = Read(), M2 = Read() ;
    for (RE int i = 1 ; i <= N ; i ++)
    for (RE int j = 1 ; j <= N ; j ++)
        Dist[i][j] = Inf ;
    for (RE int i = 1 ; i <= M1 ; i ++) {
        int X = Read(), Y = Read() ;
        Add(X, Y, 1) ; Add(Y, X, - 1) ;
        Dist[X][Y] = min(Dist[X][Y], 1) ;
        Dist[Y][X] = min(Dist[Y][X],  - 1) ;
    }
    for (RE int i = 1 ; i <= N ; i ++) Dist[i][i] = 0 ;
    for (RE int i = 1 ; i <= M2 ; i ++) {
        int X = Read(), Y = Read() ;
        Add(Y, X, 0) ;
        Dist[Y][X] = min(Dist[Y][X], 0) ;
    }
    for (RE int i = 1 ; i <= N ; i ++)
        if (! Dfn[i]) Tarjan(i) ;
    for (RE int k = 1 ; k <= N ; k ++)
    for (RE int i = 1 ; i <= N ; i ++)
        if (B[k] == B[i])
    for (RE int j = 1 ; j <= N ; j ++)
        if (B[i] == B[j])
        Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]) ;
    for (RE int i = 1 ; i <= N ; i ++)
        if (Dist[i][i] != 0) {
            puts("NIE") ; return 0 ;
        }
    for (RE int i = 1 ; i <= N ; i ++)
    for (RE int j = 1 ; j <= N ; j ++)
        if (B[i] == B[j])
        D[B[i]] = max(D[B[i]], Dist[i][j]) ;
    for (RE int i = 1 ; i <= N ; i ++) Ans += D[i] ;
    printf("%d\n", Ans + Cnt) ; return 0 ;
}

最后发现弗洛伊德跑还是比较慢，最后加了很多 $register$ 和 $inline$ 才勉强卡过去。后来知道有一个非常神奇的深搜版 $Spfa$ ，应该是可以更好地解决这个问题的。