「6月雅礼集训 2017 Day11」tree

【题目大意】

给出一棵带权树，有两类点，一类黑点，一类白点。

求切断黑点和白点间路径的最小代价。

$n \leq 10^5$

【题解】

直接最小割能过。。但是树形dp明显更好写

设$f_{x,0/1/2}$表示$x$这个点的子树中，0表示没有带颜色的点连到这个子树的根$x$，1表示黑点连到$x$，2表示白点连到$x$。

直接转移即可。具体看代码，挺好推得。。

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const int N = 1e5 + , M = 2e5 + ;

const ll inf = 1e17;

int n, d[N];

int head[N], nxt[M], to[M], w[M], tot = ;

inline void add(int u, int v, int _w) {

    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w;

}

inline void adde(int u, int v, int _w) {

    add(u, v, _w), add(v, u, _w);

}

ll f[N][];

// 没有有颜色点连到根上，只有黑点连到根上，只有白点连到根上

inline void dp(int x, int fa = ) {

    f[x][] = inf, f[x][] = f[x][] = ;

    if(d[x] == ) f[x][] = ;

    if(d[x] == ) f[x][] = inf;

    if(d[x] == ) f[x][] = inf;

    for (int i=head[x]; i; i=nxt[i]) {

        if(to[i] == fa) continue;

        int y = to[i];

        dp(y, x);

        f[x][] += min(f[y][], min(f[y][], f[y][]) + w[i]);

        if(f[x][] > inf) f[x][] = inf;

        f[x][] += min(min(f[y][], f[y][]), f[y][] + w[i]);

        if(f[x][] > inf) f[x][] = inf;

        f[x][] += min(min(f[y][], f[y][]), f[y][] + w[i]);

        if(f[x][] > inf) f[x][] = inf;

    }

//    printf("x = %d, f[x][0] = %I64d, f[x][1] = %I64d, f[x][2] = %I64d\n", x, f[x][0], f[x][1], f[x][2]);

}

int main() {

    freopen("tree.in", "r", stdin);

    freopen("tree.out", "w", stdout);

    cin >> n;

    for (int i=, u, v, _w; i<n; ++i) {

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

        adde(u, v, _w);

    }

    int T; cin >> T;

    for (int i=, x; i<=T; ++i) {

        scanf("%d", &x);

        d[x] = ;

    }

    cin >> T;

    for (int i=, x; i<=T; ++i) {

        scanf("%d", &x);

        d[x] = ;

    }

    dp();

    cout << min(f[][], min(f[][], f[][]));

    return ;

}

/*

6

1 2 5

2 4 4

2 5 1

1 3 2

3 6 7

1

4

2

5 6

*/

巴特西

「6月雅礼集训 2017 Day11」tree

最新文章

热门文章