传送门:https://codeforces.com/problemset/problem/1108/F
求出最小生成树后处理出任意两点间边的最大值,这里可以用倍增或者树刨。然后用不在生成树上的边去替换,如果边权和边两端点路径最大边值相同则最小生成树不唯一,需要将边权\(+1\)。实现比较简单,写了一遍就过了。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
int res = c - '0';
while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
return flag ? -res : res;
}
const int N = 2e5 + 1;
int Max[N][22], fa[N][22], head[N], cnt, ff[N], dep[N];
struct Edge {
int v, next, w;
} e[N * 2];
void add(int u, int v, int w) {
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
int get(int x) { return x == ff[x] ? x : ff[x] = get(ff[x]); }
struct E {
int u, v, w, use;
bool operator<(const E &o) const { return w < o.w; }
} edge[N];
void dfs(int x, int f) {
dep[x] = dep[f] + 1;
fa[x][0] = f;
for (int i = 1; i <= 20; ++i) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
Max[x][i] = max(Max[x][i - 1], Max[fa[x][i - 1]][i - 1]);
}
for (int i = head[x]; ~i; i = e[i].next) {
int y = e[i].v;
if (y == f) continue;
Max[y][0] = e[i].w;
dfs(y, x);
}
}
int getMax(int x, int y) {
int ans = 0;
if (dep[x] > dep[y]) swap(x, y);
for (int i = 21; i >= 0; --i) if (dep[fa[y][i]] >= dep[x]) ans = max(ans, Max[y][i]), y = fa[y][i];
if (x == y) return ans;
for (int i = 21; i >= 0; --i)
if (fa[x][i] != fa[y][i])
ans = max(ans, max(Max[x][i],
Max[y][i])), x = fa[x][i], y = fa[y][i];
return max(ans, max(Max[x][0], Max[y][0]));
}
int main() {
int ans = 0;
memset(head, -1, sizeof head);
int n = read(), m = read();
for (int i = 1; i <= n; ++i) ff[i] = i;
for (int i = 1; i <= m; ++i) edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
sort(edge + 1, edge + m + 1);
for (int i = 1; i <= m; ++i) {
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (get(u) != get(v)) {
ff[get(u)] = get(v);
add(u, v, w);
add(v, u, w);
edge[i].use = 1;
}
}
dfs(1, 0);
for (int i = 1; i <= m; ++i) if (!edge[i].use) if (edge[i].w == getMax(edge[i].u, edge[i].v)) ++ans;
printf("%d", ans);
return 0;
}
标签:max,int,题解,ans,CF1108F,fa,read,Max
From: https://www.cnblogs.com/Jefferyz/p/18447425