又是一个清奇的脑回路, 也考验对算法的理解深度

懵逼的 题目

传送至 Vijos

扯淡的 题解

只会打$n ^ 2$暴力, 剩下啥都不会了

首先考虑Kruskal选一条边的时候, 条件是 [当前边的两个顶点不在一个连通分量里, 而且这一条边是连接两个连通分量的权值最小的边] 所以当我们得知了一条最小生成树的边时, 我们就知道, 这两个连通分量之间所有的连边都要比这条边大, 所以我们可以:

  • 按边的权值从小到大排序, 因为Kruskal是从小到大, 我们要根据Kruskal推出答案
  • 对于当前的这条边, 找到两个顶点所属的连通分量的大小, 相乘即为这两个连通分量之间要连的边
  • 合并这两个连通分量
    没了

沙茶的 代码

60分大暴力

//暴力

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (20000 + 5)
#define LL long long
using namespace std;
struct edg
{
    int from;
    int to;
    int cost;
    int next;
} b[MAXN << 1];
int cntb;
int g[MAXN];
int n;
LL ans;
int fa[MAXN];
void solve();
void dfs(int, int, bool);
void adn(int, int, int);
int main()
{
    scanf("%d", &n);
    int srx, sry, srz;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        adn(srx, sry, srz);
        adn(sry, srx, srz);
    }
    solve();
    ans >>= 1;
    printf("%lld", ans);
    return 0;
}
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        memset(fa, 0, sizeof(fa));
        for (int j = g[i]; j; j = b[j].next)
        {
            fa[b[j].to] = i;
            dfs(b[j].to, b[j].cost, true);
        }
    }
}
void dfs(int dq, int dqmax, bool sf)
{
    ans += dqmax;
    ans += (sf ? 0 : 1);
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != fa[dq])
        {
            fa[b[i].to] = dq;
            dfs(b[i].to, max(dqmax, b[i].cost), false);
        }
    }
}

AC

// Vijos1579改

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (20000 + 5)
#define LL long long 
using namespace std;
struct edg
{
    int from;
    int to;
    LL cost;
}b[MAXN];
int n;
LL ans;
int rak[MAXN];
int fa[MAXN];
bool cmp(edg, edg);
void solve();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost);
    }
    solve();
    ans -= (n - 1);
    printf("%lld", ans);
    return 0;
}
bool cmp(edg x, edg y)
{
    return x.cost < y.cost;
}
int find(int x)
{
    return x == fa[x] ? (x) : (fa[x] = find(fa[x]));
}
void uni(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    rak[fx] += rak[fy];
    fa[fy] = fx;
}
void solve()
{
    sort(b + 1, b + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        rak[i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        int x = b[i].from;
        int y = b[i].to;
        int fx = find(x);
        int fy = find(y);
        ans += (LL) rak[fx] * rak[fy] * (b[i].cost + 1);
        uni(x, y);
    }
}

/*
4
1 2 1
1 3 1
1 4 2

*/
/*
3 
1 2 4 
2 3 7

*/

By 没写作业被D飞的 Cansult