学步园

题目抽象：给你一棵树，然后再给你一些点，破坏每一个点都有一些时间，现在要你求让任意给定两个定点之间都互相隔离，所需要的最少时间？

解体思路：1.树DP，因为无后效性，因此DP是没有问题的，关键是如和写程序的问题，快要走人了，待会再补...

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100010;
int vertex[MAXN];
bool color[MAXN];
bool mac[MAXN];
int E;

struct Edge {
    int u, v, c;
    int next;

    void set(int uu, int vv, int cc) {
        u = uu, v = vv, c = cc;
    }
} edge[2 * MAXN];

void init() {
    E = 0;
    memset(vertex, -1, sizeof (vertex));
    memset(color, 0, sizeof (color));
    memset(mac, false, sizeof (mac));
}

void AddEdge(int u, int v, int c) {
    edge[E].set(u, v, c);
    edge[E].next = vertex[u];
    vertex[u] = E++;

    edge[E].set(v, u, c);
    edge[E].next = vertex[v];
    vertex[v] = E++;
}

long long res;

int DFS(int u) {
    color[u] = true;
    long long sum = 0;
    int max_c = 0;
    for (int now = vertex[u]; now != -1; now = edge[now].next) {
        int next = edge[now].v;
        if (!color[next]) {
            if (mac[next]) {
                max_c = max(max_c, edge[now].c);
                sum += edge[now].c;
                DFS(next);
            } else {
                int a = min(DFS(next), edge[now].c);
                sum += a;
                max_c = max(max_c, a);
            }
        }
    }
    res += sum;
    if (!mac[u]) {
        res -= max_c;
    }
    return max_c;
}

int main() {
    int T;
    scanf("%d", &T);
    int N, K;
    int x, y, t;
    while (T--) {
        scanf("%d%d", &N, &K);
        init();
        for (int i = 0; i < N - 1; i++) {
            scanf("%d%d%d", &x, &y, &t);
            AddEdge(x, y, t);
        }
        int k;
        for (int i = 0; i < K; i++) {
            scanf("%d", &k);
            mac[k] = true;
        }
        res = 0;
        DFS(0);
        printf("%Id\n", res);
    }
    return 0;
}

2.贪心算法

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int father[MAXN];
bool color[MAXN];
int N, K;

void init() {
    for (int i = 0; i < MAXN; i++) {
        father[i] = i;
    }
}

struct Edge {
    int u, v, c;

    bool operator<(const Edge & a)const {
        return c > a.c;
    }
} edge[MAXN];

int find_ancest(int x) {
    if (x == father[x]) return x;
    return father[x] = find_ancest(father[x]);
}

long long get_result() {
    init();
    sort(edge + 1, edge + N);
    long long res = 0;
    for (int i = 1; i < N; i++) {
        int u, v;
        u = find_ancest(edge[i].u);
        v = find_ancest(edge[i].v);
        if (!color[v]) {
            father[v] = u;
        } else if (!color[u] && color[v]) {
            father[u] = v;
        } else {
            res += edge[i].c;
        }
    }
    return res;
}

int main() {
    int T;
    int x, y, t;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &K);
        for (int i = 1; i < N; i++) {
            scanf("%d%d%d", &x, &y, &t);
            edge[i].u = x, edge[i].v = y, edge[i].c = t;
        }
        int k;
        memset(color, 0, sizeof (color));
        for (int i = 0; i < K; i++) {
            scanf("%d", &k);
            color[k] = true;
        }
        printf("%I64d\n", get_result());
    }

    return 0;
}