国王要到达每一个点要求图不能有环, 所以按照要求, 去掉墙的数量少, 去掉墙的花费小, 可转化为最大生成树求解
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int MAXN = 200010;struct _Edge {int u, v, cost;bool operator<(const _Edge rhs) const { return cost > rhs.cost; }
};_Edge E[MAXN];
int f[MAXN];int Find(int x) { return f[x] == -1 ? x : f[x] = Find(f[x]); }
bool Union(int a, int b) {int x = Find(a);int y = Find(b);f[y] = x;return x != y;
}
int main() {int n, m, total, num;while (scanf("%d%d", &n, &m) != EOF) {total = 0;num = 0;for (int i = 0; i < MAXN; ++i)f[i] = -1;for (int i = 1; i <= n; ++i) {int x, y;cin >> x >> y;}for (int i = 0; i < m; ++i) {cin >> E[i].u >> E[i].v >> E[i].cost;total += E[i].cost;}sort(E, E + m);for (int i = 0; i < m; ++i) {if (Find(E[i].u) != Find(E[i].v)) {Union(E[i].u, E[i].v);num++;total -= E[i].cost;}}printf("%d %d\n", m - num, total);}return 0;
}