Link
一道非常好的差分约束系统的板子题，正好可以借此回顾一下差分约束的有关内容。
假设我们现在有N个方程，
$X_1 - X_2 \leq 0$
$X_1 - X_5 \leq 1$
$X_2 - X_5 \leq 1$
$X_3 - X_1 \leq 5$
$X_4 - X_1 \leq 4$
$X_4 - X_3 \leq - 1$
$X_5 - X_3 \leq - 3$
$X_5 - X_4 \leq - 3$
这样第一个方程组，我们当然可以解不等式组，但是如果我们要求电脑计算的话就需要一些方法，比如说最短路
对于这道题来说，我们对于每一种情况。
- Add(X, Y, 0), Add(Y, X, 0) ;
- Add(X, Y, 1) ;
- Add(Y, X, 0) ;
- Add(Y, X, 1) ;
- Add(X, Y, 0) ;
并且还要特判一下当$Type = 2$ 或 $4$ 的时候，如果$X == Y$那么久一定是没有解的。
然后直接跑SPFA就是了。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
using namespace std ;
typedef long long LL ;
const LL MAXN = 1000100 ;
const LL MAXM = 1000100 ;
const LL Inf = 1000000000 ;
inline LL Read() {
LL 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 ;
}
LL N, M, H[MAXN], Tot, D[MAXN], INQ[MAXN], F, Num[MAXN] ;
struct Node {
LL F, T, L, Next ;
} E[MAXM << 1] ;
inline void Add(LL F, LL T, LL L) {
E[++ Tot].F = F ; E[Tot].T = T ; E[Tot].L = L ;
E[Tot].Next = H[F] ; H[F] = Tot ;
}
inline long long Spfa(LL S) {
queue <LL> Q ;
for (register LL i = 1 ; i <= N ; i ++)
D[i] = 0, INQ[i] = 0, Num[i] = 0 ;
Q.push(S) ; D[S] = 0 , INQ[S] = 1 ;
while (! Q.empty()) {
LL Now = Q.front() ; Q.pop() ; INQ[Now] = 0 ;
if (Num[Now] == N - 1) return - 1 ; Num[Now] ++ ;
for (register LL i = H[Now] ; i ; i = E[i].Next)
if (D[E[i].T] < D[Now] + E[i].L) {
D[E[i].T] = D[Now] + E[i].L ;
if (! INQ[E[i].T])
Q.push(E[i].T), INQ[E[i].T] = 1 ;
}
} long long Ans = 0 ;
for (LL i = 1 ; i <= N ; i ++) Ans += D[i] ;
return Ans ;
}
int main() {
//freopen("testdata.in", "r", stdin) ;
N = Read() ; M = Read() ;
for (register LL i = 1 ; i <= M ; i ++) {
LL Type = Read(), X = Read(), Y = Read() ;
if (Type == 1) Add(X, Y, 0), Add(Y, X, 0) ;
if (Type == 2) Add(X, Y, 1) ;
if (Type == 3) Add(Y, X, 0) ;
if (Type == 4) Add(Y, X, 1) ;
if (Type == 5) Add(X, Y, 0) ;
if (Type == 2 || Type == 4)
if (X == Y)
return puts("-1"), 0 ;
}
for (register LL i = N ; i >= 1 ; i --)
Add(0, i, 1) ;
printf("%lld\n", Spfa(0)) ;
}