传送门

题目大意:给咱一颗树,每条边有权值,要使得跟节点与叶子节点不相连,最少代价是多少。

思路:这题之前自己就想象过,居然真的有这道题hhh，考虑树形dp,找某颗子树的跟与所有叶子节点

不相连的最小代价x,假设正在计算的树为x1,子树的x2是100,而与子树相连的边的权值w是70,则直接删除向连边即可,

如果与子树相连的边的权值是120,那么就要加上x2,即x1+=min(w,x2);所以把叶子节点的x设置为inf,即可一次dfs求出结果啦。

然而这题还可以用最小割的方法解决,我们把叶子节点与汇点相连,容量设置为inf,根节点就是源点,然后找最小割即可。

树形dp:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
const ll inf =LONG_MAX;
struct edge {
    int f, t, nxt;
    ll w;
}e[maxn];
int hd[maxn], tot = 1;
void add(int f, int t, ll w) {
    e[++tot] = { f,t,hd[f],w };
    hd[f] = tot;
}
int n, root;
int du[maxn];
ll dfs(int u,int f) {
    if (du[u]==1&&u!=root)return inf;//度为1,排除根就是叶子
    ll sum = 0,flg=0;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].t;ll w = e[i].w;
        if (v == f)continue;
        sum += min(w, dfs(v,u));
    }
    return sum;
}
int main() {
    //freopen("test.txt", "r", stdin);
    scanf("%d%d", &n, &root);
    for (int i = 1; i < n; i++) {
        int a, b;ll c; scanf("%d%d%lld", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
        du[a]++; du[b]++;
    }
    printf("%lld\n", dfs(root,-1));
    return 0;
}

最小割:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 600005;
const int inf = 0x3f3f3f3f;
struct edge {
    int f, t, nxt;
    ll flow;
}e[maxn * 2];
int hd[maxn], tot = 1;
void add(int f, int t, ll flow) {
    e[++tot] = { f,t,hd[f],flow };
    hd[f] = tot;
}
int n, root;
int s, d;
int dep[maxn], cur[maxn];
bool bfs() {//找增广路
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    queue<int>Q;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = hd[u]; i; i = e[i].nxt) {
            int v = e[i].t, flow = e[i].flow;
            if (flow > 0 && !dep[v]) {
                dep[v] = dep[u] + 1;
                if (v == d)return true;
                Q.push(v);
            }
        }
    }
    return false;
}
ll dfs(int u, ll flow) {
    if (u == d)return flow;
    ll last = flow;
    for (int i = cur[u]; i; i = e[i].nxt) {
        cur[u] = i;//当前弧优化
        int v = e[i].t; ll flow = e[i].flow;
        if (flow > 0 && dep[v] == dep[u] + 1) {
            ll tmp = dfs(v, min(last, flow));
            last -= tmp;
            e[i].flow -= tmp;
            e[i ^ 1].flow += tmp;
            if (last == 0)break;//流量没了直接退出循环,与当前弧优化对应
        }
    }
    if (last == flow)dep[u] = 0;//从当前点一点流量没流到终点(未找到增广路),炸点优化
    return flow - last;//返回剩余流量
}
ll dinic() {
    ll maxflow = 0;
    while (bfs()) {
        memcpy(cur, hd, sizeof(hd));
        maxflow += dfs(s, inf);
    }
    return maxflow;
}
void dfs1(int u, int f) {//找叶子顺便确定反向边
    bool h = 0;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].t;
        if (v == f)continue;
        dfs1(v, u);
        e[i ^ 1].flow = 0;//另一条边就是反向边,流量设置为0
        h = 1;
    }
    if (!h)add(u, d, inf), add(d, u, 0);//叶子与汇点建边
}
int main() {
    //freopen("test.txt", "r", stdin);
    scanf("%d%d", &n, &root);
    for (int i = 1; i < n; i++) {
        int a, b;ll c; scanf("%d%d%lld", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    s = root, d = n + 1;
    dfs1(root,-1);
    printf("%lld\n", dinic());
    return 0;
}