Codeforces 868E Policeman and a Tree

题意简述

给你一颗有n个点的树，每条边有边权，有一个警察一开始在点S，他的速度是1，即通过一条长度为x的边要花x单位时间。

有m个罪犯，一开始第i个在点x[i]，他们的速度无限快。

如果罪犯和警察到达同一个点，那么罪犯会被抓住。

现在罪犯们想最大化最后一个被抓的时间，警察想最小化抓的时间。

求警察抓住所以罪犯的时间的最小值

题解思路

dp

dp[u][v][x][y] 表示从u走向v，以v为根的子树有x个罪犯，其余有y个罪犯

然后进行转移

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

const int INF = 0x3f3f3f3f;

int n, m, s, u, v, w, tmp, cnt, ans = INF, xx;

int h[60], nxt[120], to[120], c[60], sz[60];

int dis[60][60], f[2][60];

int dp[60][60][60][60];

inline mmin(int& x, const int& y) {if (x > y) x = y; }

inline mmax(int& x, const int& y) {if (x < y) x = y; }

inline void add_edge(const int& u, const int& v)

{

    to[++cnt] = v;

    nxt[cnt] = h[u];

    h[u] = cnt;

}

void dfs(const int& u, const int& fa)

{

    for (register int i = h[u]; i; i = nxt[i])

        if (to[i] != fa)

        {

            dfs(to[i], u);

            c[u] += c[to[i]];

        }

}

int solve(const int& u, const int& v, const int& x, const int& y)

{

    if (!x && !y) return 0;

    if (!x) return INF;

    if (dp[u][v][x][y] < INF) return dp[u][v][x][y];

    if (sz[v] == 1) return (dp[u][v][x][y] = (solve(v, u, y, 0) + dis[u][v]));

    for (register int i = h[v]; i; i = nxt[i])

        if (to[i] != u)

            for (register int j = 0; j <= x; ++j)

                solve(v, to[i], j, x + y - j);

    memset(f[1], 0, sizeof(f[1]));

    f[tmp = 1][0] = INF;

    for (register int i = h[v]; i; i = nxt[i])

        if (to[i] != u)

        {

            tmp ^= 1;

            memset(f[tmp], 0, sizeof(f[tmp]));

            for (register int j = 0; j <= x; ++j)

                for (register int k = 0; j + k <= x; ++k)

                {

                    xx = solve(v, to[i], k, x + y - k);

                    mmax(f[tmp][j + k], std::min(f[tmp ^ 1][j], xx));

                }

        }

    return (dp[u][v][x][y] = (f[tmp][x] + dis[u][v]));

}

int main()

{

    scanf("%d", &n);

    for (register int i  = 1; i < n; ++i)

    {

        scanf("%d%d%d", &u, &v, &w);

        add_edge(u, v); add_edge(v, u);

        dis[u][v] = dis[v][u] = w;

        ++sz[u]; ++sz[v];

    }

    scanf("%d%d", &s, &m);

    for (register int i = 1; i <= m; ++i) { scanf("%d", &tmp); ++c[tmp]; }

    dfs(s, 0);

    memset(dp, INF, sizeof(dp));

    for (register int i = h[s]; i; i = nxt[i])

        mmin(ans, solve(s, to[i], c[to[i]], m - c[to[i]]));

    printf("%d\n", ans);

}

巴特西

Codeforces 868E Policeman and a Tree

题意简述

题解思路

代码

最新文章

热门文章