BZOJ1143: [CTSC2008]祭祀river

Description

　　在遥远的东方，有一个神秘的民族，自称Y族。他们世代居住在水面上，奉龙王为神。每逢重大庆典， Y族都

会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着

两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（下图描述一个环流的例子）。

　　由于人数众多的原因，Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重，这些祭祀地点的选择必

须非常慎重。准确地说，Y族人认为，如果水流可以从一个祭祀点流到另外一个祭祀点，那么祭祀就会失去它神圣

的意义。族长希望在保持祭祀神圣性的基础上，选择尽可能多的祭祀的地点。

Input

第一行包含两个用空格隔开的整数N、M，分别表示岔口和河道的数目，岔口从1到N编号。

接下来M行，每行包含两个用空格隔开的整数u、v，

描述一条连接岔口u和岔口v的河道，水流方向为自u向v。

N≤100M≤1000

Output

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

Sample Input

4 4
1 2
3 4
3 2
4 2

Sample Output

2
【样例说明】
在样例给出的水系中，不存在一种方法能够选择三个或者三个以上的祭祀点。包含两个祭祀点的测试点的方案有两种：
选择岔口1与岔口3（如样例输出第二行），选择岔口1与岔口4。
水流可以从任意岔口流至岔口2。如果在岔口2建立祭祀点，那么任意其他岔口都不能建立祭祀点
但是在最优的一种祭祀点的选取方案中我们可以建立两个祭祀点，所以岔口2不能建立祭祀点。对于其他岔口
至少存在一个最优方案选择该岔口为祭祀点，所以输出为1011。

HINT

Source

本题的做法很妙，首先本题等价于求最小链覆盖。经典的最小链覆盖可以把原图中的一个点拆为左右两个点。对于原图中的有向边(u,v)，但是这里的链却可以在节点处重合。怎样构图就成了一个问题。发现一条链可以在点处相交其实就等价于在原图中一个点可以与[它向下能到达的所有点]相连(可以理解为只要可以到达，可以"绕过"被占用的点)。正确性为什么是对的呢？不难发现，因为要用最少的链数来覆盖所有点，那么链长一定要最长。这样的话我们如果跳过[被占用的点以外的其他点]是不会使解更优的。那么我们只需要先用Floyd做一遍传递闭包，然后把每个点和它所能到达的所有点在二分图中连边就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 5e2 + 5;
const int maxm = 1e4 + 5;
bool dp[maxn][maxn];
struct edge {
    int v, w, next;
}e[maxm << 1];
int head[maxn], cnt, u, v, n, m, cur[maxn];
void adde(const int &u, const int &v, const int &w) {
    e[cnt] = (edge) {v, w, head[u]};
    head[u] = cnt++;
    e[cnt] = (edge) {u, 0, head[v]};
    head[v] = cnt++;
}
void floyd(int n) {
    for(register int k = 1; k <= n; ++k)
        for(register int i = 1; i <= n; ++i)
            for(register int j = 1; j <= n; ++j)
                dp[i][j] |= dp[i][k] & dp[k][j];
}
const int L = 0, R = 1;
int layer[maxn];
bool bfs(int s, int t) {
    queue<int > q;
    memset(layer, 0, sizeof(layer));
    q.push(s), layer[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(register int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(!e[i].w || layer[v]) continue;
            layer[v] = layer[u] + 1, q.push(v);
        }
    }
    return layer[t];
}
int dfs(int u, int t, int f) {
    int inc = 0, ret;
    if(u == t) return f;
    for(register int &i = cur[u]; ~i && f - inc > 0; i = e[i].next) {
        int v = e[i].v;
        if(!e[i].w || layer[v] != layer[u] + 1) continue;
        ret = dfs(v, t, min(e[i].w, f - inc));
        if(ret) {
            e[i].w -= ret;
            e[i ^ 1].w += ret;
            inc += ret;
        }
    }
    return inc;
}
int dinic(int s, int t) {
    int ans = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(cur));
        ans += dfs(s, t, 0x3f3f3f3f);
    }
    return ans;
}
int p[maxn][2], pcnt, S, T;
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= m; ++i) 
        scanf("%d%d", &u, &v), dp[u][v] = 1;
    floyd(n);
    S = pcnt = 1;
    for(register int i = 1; i <= n; ++i)
        p[i][L] = ++pcnt, p[i][R] = ++pcnt;
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            if(dp[i][j]) 
                adde(p[i][L], p[j][R], 1);
    T = ++pcnt;
    for(register int i = 1; i <= n; ++i)
        adde(S, p[i][L], 1), adde(p[i][R], T, 1);
    printf("%d\n", n - dinic(S, T));
    return 0;
}

Rockdu's Blog