「BZOJ1143」[CTSC2008]祭祀river

Description

在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。

由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必
须非常慎重。准确地说,Y族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失去它神圣
的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。

Input

第一行包含两个用空格隔开的整数NNMM,分别表示岔口和河道的数目,岔口从11NN编号。
接下来MM行,每行包含两个用空格隔开的整数uuvv
描述一条连接岔口uu和岔口vv的河道,水流方向为自uuvv

Output

第一行包含一个整数KK,表示最多能选取的祭祀点的个数。

Sample Input

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

Sample Output

1
2

HINT

N100,M1000N\leq 100,M\leq1000

Solution

最小路径覆盖
切这题前你要先做了这题。
现在假设你会求最小路径覆盖了。
我们现在就是求最长反链=最小路径覆盖。
用Floyd跑传递闭包,每两个能到达的点直接连一条(x,y,1)(x,y,1)边,第三个是容量。
很显然,所有设立的祭祀点可以形成DAG,他们必须是反链里的点。这等于最小链覆盖。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#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 = 120*2, M = 120 * 120*3;
bool g[N][N];
struct Edge {
int u, v, f, nxt;
}e[M * 2];
int head[N], en = 1;
int n, m, s, t;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = 1;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int d[N];
bool bfs() {
queue<int>q;
q.push(s);
memset(d, 0, sizeof d);
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
// printf("x=%d\n", x);
for(int i = head[x]; i; i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1 && e[i].f) {
k = dinic(e[i].v, min(e[i].f, rest));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
int pre[N], nxt[N];
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
g[x][y] = 1;
}
s = n * 2 + 1;
t = n * 2 + 2;
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n && !g[i][j]; ++j)
g[i][j] |= (g[i][k] && g[k][j]);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(g[i][j] && i != j) {
addedge(i, j + n);
}
for(int i = 1; i <= n; ++i) {
addedge(s, i);
addedge(i + n, t);
}
int ans = 0, y;
while(bfs()) while(y = dinic(s, 1e9)) ans += y;
writeln(n - ans);
return 0;
}