Link
看到题目首先肯定想到差分约束，当然这也是一个差分约束的题。
题目比较难想的地方在于建图，设$Dist[i][j]$表示$max\{A_i - A_j\}$，也就是$A_i$最多能比$A_j$大多少。那么根据题意我们知道对于第一种情况，应该是
然后对于第二种情况，题目对数量上并没有限制，限制的只是大小关系，然而我们转化一下依然能知道$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$的最大差值，于是就可以寻找每一个强联通分量里面的最大值。并且每一个强联通分量在数值上没有关系，因此将答案直接累加即可，最后输出答案加上强连通分量的数量。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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90// luogu-judger-enable-o2
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$，应该是可以更好地解决这个问题的。