2010-1136

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题意 ==
从左往右分布着有N个跳板，在地上时可以跳到任意一个跳板上，而处于一个高度为h的跳板上可以跳到右边的高度处在[h, h + H]之间跳板上，每个跳板只能被跳一次。现在有许多小朋友要来跳这些跳板，每一个跳跳板的人会跳尽可能多的跳板，同时如果一个人发现自己跳的跳板数不可能达到前面某个小朋友所跳的跳板数，他就不玩了（也就是说每个人跳的跳板数必须都是一开始的最大值）。现在你需要做出安排，使尽可能多的小朋友享受跳板的乐趣。

== 题解 ==
题意有点难懂，我们来抽象一下。把每个跳板看成一个点，如果可以从跳板u跳到跳板v，那么连一条(u, v)的边，这样就构成了一个有向无环图(DAG)，题目实际上要求的是这个DAG中的不相交最长路径的条数。首先用DP求一下到每个点的最长路dp[i]，通过方程dp[i] = max{dp[j] + 1, 0 <= j < i 并且存在边(j, i)}。然后保留满足dp[i] == dp[j] + 1的边(j, i)，其他的边和最长路无关于是删掉。然后从添加源汇s,t，对于每个入度为0的点v，连一条边(s, v), 对每个出度为0的点u，连一条边(u, t)。求一下最大流，就得到了答案。

== 代码 ==


{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 1024
#define INF 1000000000
#define MAXE MAXN*MAXN
class Dinic {
    int n, m, src, dst, head[MAXN], work[MAXN], d[MAXN];
    struct edge {
        int v, f, c, nxt;
        edge() {}
        edge(int v, int f, int c, int nxt): v(v), f(f), c(c), nxt(nxt) {}
    } e[MAXE];
    bool _bfs() {
        int q[MAXN], le, ri;
        le = ri = 0;
        memset(d, -1, sizeof(int) * n);
        q[ri++] = src;
        d[src] = 0;
        while(le < ri) {
            for(int k = q[le++], i = head[k]; i != -1; i = e[i].nxt) {
                if(e[i].f < e[i].c && d[e[i].v] == -1) {
                    d[e[i].v] = d[k] + 1;
                    q[ri++] = e[i].v;
                }
            }
        }
        return (d[dst] != -1);
    }
    int _dfs(int u, int f) {
        if(u == dst) 
            return f;
        for(int& i = work[u]; i != -1; i = e[i].nxt) {
            if(e[i].f < e[i].c && d[e[i].v] == d[u] + 1) {
                int minf = _dfs(e[i].v, min(f, e[i].c - e[i].f));
                if(minf > 0) {
                    e[i].f += minf;
                    e[i ^ 1].f -= minf;
                    return minf;
                }
            }
        }
        return 0;
    }
public:
    void init(int n, int src, int dst) {
        this->n = n;
        this->src = src;
        this->dst = dst;
        m = 0;
        memset(head, -1, sizeof(int) * n);
    }
    void addEdge(int u, int v, int c, int rc) {
        e[m] = edge(v, 0, c, head[u]);
        head[u] = m++;
        e[m] = edge(u, 0, rc, head[v]);
        head[v] = m++;
    }
    int maxFlow() {
        int ret = 0;
        while(_bfs()) {
            memcpy(work, head, sizeof(int) * n);
            while(true) {
                int delta;
                delta = _dfs(src, INF);
                if(delta == 0)
                    break;
                ret += delta;
            }
        }
        return ret;
    }
} dinic;
int a[MAXN], dp[MAXN];
int main() {
    int n, h;
    while(scanf("%d%d", &n, &h) != EOF) {
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(int) * n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < i; ++j) {
                if(a[j] <= a[i] && a[i] <= a[j] + h) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        dinic.init(n + 2, n, n + 1);
        int mt = -1;
        for(int i = 0; i < n; ++i) {
            mt = max(mt, dp[i]);
            for(int j = 0; j < i; ++j) {
                if(a[j] <= a[i] && a[i] <= a[j] + h && dp[i] == dp[j] + 1) {
                    dinic.addEdge(j, i, 1, 0);
                }
            }
        }
        for(int i = 0; i < n; ++i) {
            if(dp[i] == 0)
                dinic.addEdge(n, i, 1, 0);
            if(dp[i] == mt)
                dinic.addEdge(i, n + 1, 1, 0);
        }
        printf("%d\n", dinic.maxFlow());
    }
}
}}}

题意

从左往右分布着有N个跳板，在地上时可以跳到任意一个跳板上，而处于一个高度为h的跳板上可以跳到右边的高度处在[h, h + H]之间跳板上，每个跳板只能被跳一次。现在有许多小朋友要来跳这些跳板，每一个跳跳板的人会跳尽可能多的跳板，同时如果一个人发现自己跳的跳板数不可能达到前面某个小朋友所跳的跳板数，他就不玩了（也就是说每个人跳的跳板数必须都是一开始的最大值）。现在你需要做出安排，使尽可能多的小朋友享受跳板的乐趣。

题解

题意有点难懂，我们来抽象一下。把每个跳板看成一个点，如果可以从跳板u跳到跳板v，那么连一条(u, v)的边，这样就构成了一个有向无环图(DAG)，题目实际上要求的是这个DAG中的不相交最长路径的条数。首先用DP求一下到每个点的最长路dp[i]，通过方程dp[i] = max{dp[j] + 1, 0 <= j < i 并且存在边(j, i)}。然后保留满足dp[i] == dp[j] + 1的边(j, i)，其他的边和最长路无关于是删掉。然后从添加源汇s,t，对于每个入度为0的点v，连一条边(s, v), 对每个出度为0的点u，连一条边(u, t)。求一下最大流，就得到了答案。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 1024
#define INF 1000000000
#define MAXE MAXN*MAXN
class Dinic {
    int n, m, src, dst, head[MAXN], work[MAXN], d[MAXN];
    struct edge {
        int v, f, c, nxt;
        edge() {}
        edge(int v, int f, int c, int nxt): v(v), f(f), c(c), nxt(nxt) {}
    } e[MAXE];
    bool _bfs() {
        int q[MAXN], le, ri;
        le = ri = 0;
        memset(d, -1, sizeof(int) * n);
        q[ri++] = src;
        d[src] = 0;
        while(le < ri) {
            for(int k = q[le++], i = head[k]; i != -1; i = e[i].nxt) {
                if(e[i].f < e[i].c && d[e[i].v] == -1) {
                    d[e[i].v] = d[k] + 1;
                    q[ri++] = e[i].v;
                }
            }
        }
        return (d[dst] != -1);
    }
    int _dfs(int u, int f) {
        if(u == dst) 
            return f;
        for(int& i = work[u]; i != -1; i = e[i].nxt) {
            if(e[i].f < e[i].c && d[e[i].v] == d[u] + 1) {
                int minf = _dfs(e[i].v, min(f, e[i].c - e[i].f));
                if(minf > 0) {
                    e[i].f += minf;
                    e[i ^ 1].f -= minf;
                    return minf;
                }
            }
        }
        return 0;
    }
public:
    void init(int n, int src, int dst) {
        this->n = n;
        this->src = src;
        this->dst = dst;
        m = 0;
        memset(head, -1, sizeof(int) * n);
    }
    void addEdge(int u, int v, int c, int rc) {
        e[m] = edge(v, 0, c, head[u]);
        head[u] = m++;
        e[m] = edge(u, 0, rc, head[v]);
        head[v] = m++;
    }
    int maxFlow() {
        int ret = 0;
        while(_bfs()) {
            memcpy(work, head, sizeof(int) * n);
            while(true) {
                int delta;
                delta = _dfs(src, INF);
                if(delta == 0)
                    break;
                ret += delta;
            }
        }
        return ret;
    }
} dinic;
int a[MAXN], dp[MAXN];
int main() {
    int n, h;
    while(scanf("%d%d", &n, &h) != EOF) {
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(int) * n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < i; ++j) {
                if(a[j] <= a[i] && a[i] <= a[j] + h) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        dinic.init(n + 2, n, n + 1);
        int mt = -1;
        for(int i = 0; i < n; ++i) {
            mt = max(mt, dp[i]);
            for(int j = 0; j < i; ++j) {
                if(a[j] <= a[i] && a[i] <= a[j] + h && dp[i] == dp[j] + 1) {
                    dinic.addEdge(j, i, 1, 0);
                }
            }
        }
        for(int i = 0; i < n; ++i) {
            if(dp[i] == 0)
                dinic.addEdge(n, i, 1, 0);
            if(dp[i] == mt)
                dinic.addEdge(i, n + 1, 1, 0);
        }
        printf("%d\n", dinic.maxFlow());
    }
}