Forsaken喜欢独一无二的树

题意：

分析：

正如“jxnu-19-软技一班-刘晟”所说的，按照kruskai算法的想法来看的话，出现多条最短路径的原因只可能是存在复数的最小权值边连接着两个集合以供选择。
那我们其实只要在kruskai算法进行的同时动手脚就行了。
我们先对权值进行从小到大的排序，然后将其分为一个个的相等权值的集合。
对每一份的相等权值集合，我们看这里面有没有复数的连接两个集合的边，有的话我们实际上只需连一条，所以剩下的条数*权值就是我们要消去的。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int max_n = 2e5 + 100;
typedef pair<int, int> pii;
struct edge
{
    int u, v, cost;
    bool operator<(const edge& e) { return cost < e.cost; }
}E[max_n];
int n, m;

int par[max_n];
int rak[max_n];

void init(int n) {
    for (int i = 1;i <= n;i++)par[i] = i;
    fill(rak, rak + 1 + n, 0);
}

int find(int x) {
    if (par[x] == x)return x;
    else return par[x] = find(par[x]);
}

bool same(int x, int y) {
    return find(x) == find(y);
}

bool merge(int x, int y) {
    if ((x = find(x)) == (y = find(y)))return false;
    if (rak[x] > rak[y])par[y] = x;
    else if (rak[x] < rak[y])par[x] = y;
    else par[y] = x, rak[x]++;
    return true;
}

ll kruskai_change() {
    ll ans = 0;init(n);
    sort(E + 1, E + 1 + m);
    int i = 1;int j = 1;
    while (i <= m) {
        while ((j <= m) && (E[j].cost == E[i].cost))j++;
        for (int k = i;k < j;k++) {
            int u = E[k].u;int v = E[k].v;
            if (!same(u, v))ans += E[k].cost;
        }
        for (int k = i;k < j;k++) {
            int u = E[k].u;int v = E[k].v;
            if (!same(u, v))ans -= E[k].cost, merge(u, v);
        }
        i = j;
    }return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= m;i++)
        cin >> E[i].u >> E[i].v >> E[i].cost;
    cout << kruskai_change() << endl;
}

本题双重遍历的代码小技巧，学到了。欸嘿~