「BZOJ2788」[Poi2012]Festival

Description

nn个正整数X1,X2,,XnX_1,X_2,\cdots ,X_n,再给出m1+m2m_1+m_2个限制条件,限制分为两类:

  1. 给出a,ba,b (1a,bn)(1\leq a,b\leq n),要求满足Xa+1=XbX_a + 1 = X_b

  2. 给出c,dc,d (1c,dn)(1\leq c,d\leq n),要求满足XcXdX_c \leq X_d
    在满足所有限制的条件下,求集合{Xi}\{Xi\}大小的最大值。
    注意:题目就是求最多可以有几个不同的XiX_i取值不同。

Input

第一行三个正整数n,m1,m2(2n600,1m1+m2100,000)n, m1, m2 (2\leq n\leq 600, 1\leq m1+m2\leq 100,000)

接下来m1行每行两个正整数a,b(1a,bn)a,b (1\leq a,b\leq n),表示第一类限制。

接下来m2行每行两个正整数c,d(1c,dn)c,d (1\leq c,d\leq n),表示第二类限制。

Output

一个正整数,表示集合{Xi}\{X_i\}大小的最大值。
如果无解输出NIE。

Sample Input

1
2
3
4
5
4 2 2
1 2
3 4
1 4
3 1

Sample Output

1
3

Solution

看题目是差分约束系统。
对于条件一,建(a,b,1)(a,b,1)(b,a,1)(b,a,-1)
对于条件二,建(c,d,0)(c,d,0)
然后让00向每一个点连(0,i,0)(0,i,0)(可以不用,向本题解代码就直接Floyd了。
00跑最长路,如果出现正环,输出无解。
很显然由条件一关联的点如果相互连通,那么一定是强连通分量。
然后每个强连通分量之间的边都是条件二建立的00边,如果00边构成了环,要么环的边权和为00这是合法的,要么不为零,那么就是非法的。不同强连通分量之间一定可以成为不同的两个值。
考虑这个强连通分量里的贡献。

由条件一限制的,那么可以发现这里面最大的不同取值就是最长链了!
图中的点是从左到右递增的关系,但是把上图其他不变,把条件一变一下,原来是xa+1=xbx_a+1=x_b,变成xb+1=xax_b+1=x_a,此时就是要取路径最小值了。
所以就是一个强连通分量里的路径最大绝对值。
注意最后可能条件一和条件二重复,记得要判断一下。

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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 610;
int n, m1, m2;
int head[N], en;
queue<int>q;
bool inq[N];
int d[N][N];
int dfn[N], low[N], num, st[N],top;
bool vis[N], g[N][N];
int scc[N], cnt, mx[N];
void tarjan(int x) {
st[++top] = x;
vis[x] = 1;
low[x] = dfn[x] = ++num;
for(int y = 1; y <= n; ++y)
if(g[x][y]) {
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if(vis[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
int y; ++cnt;
do {
y = st[top--];
vis[y] = 0;
scc[y] = cnt;
}while(x != y);
}
}
int main() {
n = read();
m1 = read();
m2 = read();
memset(d, -0x3f, sizeof d);
for(int i = 1; i <= m1; ++i) {
int x = read(), y = read();
if(d[x][y] == -1) {
puts("NIE");
return 0;
}
d[x][y] = 1;
d[y][x] = -1;
g[x][y] = g[y][x] = 1;
}
for(int i = 1; i <= m2; ++i) {
int x = read(), y = read();
if(d[x][y] == - 1) {
puts("NIE");
return 0;
}
if(d[x][y] == 1) continue;
d[x][y] = 0;
g[x][y] = 1;
}
for(int i = 1; i<= n; ++i) d[i][i] = 0;
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(d[i][k] + d[k][j] > d[i][j]) d[i][j] = d[i][k] + d[k][j];
for(int i = 1; i<= n; ++i) if(d[i][i] > 0) {
puts("NIE");
return 0;
}
for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) if(scc[i] == scc[j]) mx[scc[i]] = max(mx[scc[i]], abs(d[i][j]));
int ans = 0;
for(int i = 1; i <= cnt; ++i) ans += mx[i] + 1;
writeln(ans);
return 0;
}