ACM模版

描述

题解

这个题没有做出来我只承认我英语不好，被斯坦纳树给唬住了……没有读懂这个题真正的意图。

实际上就是给定一个树，让你将树划分为多份，然后每份内部的连通花费是固定的，求所有划分块儿的内部连通花费的和的最大值……这不就是一个求每条边贡献的吗？一个搜索就能搞定的事儿……╮(╯▽╰)╭哎，谁成想，当场我就放弃了，题都没有读懂就放弃了……真菜~~~

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1e6 + 10;

typedef long long ll;

int n, k;
int tot;
ll ans;
bool vis[MAXN];
int fount[MAXN], sz[MAXN], dis[MAXN];
int que[MAXN], pre[MAXN];

struct Edge
{
    int to, dis, net;

    Edge(int a = 0, int b = 0, int c = 0) : to(a), dis(b), net(c) {}
} edge[MAXN << 1];

void add(int u, int v, int w)
{
    edge[tot] = Edge(v, w, fount[u]);
    fount[u] = tot++;
}

void bfs(int src)
{
    memset(vis, 0, sizeof(vis));

    int head = 0, tail = 0;
    que[tail++] = src;
    vis[src] = true;

    while (tail > head)
    {
        int u = que[head++];
        sz[u] = 1;
        for (int i = fount[u]; i != -1; i = edge[i].net)
        {
            Edge e = edge[i];
            int v = e.to;
            if (vis[v])
            {
                continue;
            }
            vis[v] = true;
            que[tail++] = v;
            pre[v] = u;
            dis[v] = e.dis;
        }
    }
    for (int i = tail - 1; i >= 0; --i)
    {
        sz[pre[que[i]]] += sz[que[i]];
    }
}

void solve()
{
    bfs(1);
    ans = 0;
    for (int i = 2; i <= n; ++i)
    {
        ans += (ll)dis[i] * min(sz[i], k);
    }
}

int main()
{
    while (~scanf("%d%d", &n, &k))
    {
        memset(fount, -1, sizeof(fount));

        tot = 0;
        int u, v, w;
        for (int i = 1; i < n; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }

        solve();

        printf("%lld\n", ans);
    }

    return 0;
}