首页 > 其他分享 >CF1108F题解

CF1108F题解

时间:2024-10-04 22:44:04浏览次数:9  
标签:max int 题解 ans CF1108F fa read Max

传送门: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

相关文章

  • 题解:CF704B Ant Man
    从这来的,套路都一样,预设型DP。把那个式子拆开,看每个数单独的贡献。一个数比它左边的数小,它的贡献就是:\(-x_i+b_i\)比它左边的数大,它的贡献就是:\(x_i+a_i\)比它右边的数小,它的贡献就是:\(-x_i+d_i\)比它右边的数大,它的贡献就是:\(x_i+c_i\)即:intGl(inti){//>......
  • 题解:P8973 『GROI-R1』 继续深潜,为了同一个梦想
    换根dp模板题。\(f_i\)是在以\(i\)为根的子树中,以\(i\)为链的一个端点且\(i\)在点集中的合法点集个数。\(ans_i\)表示包含\(i\)的合法点集个数。当\(x\)为树根时:\[ans_x={f_x\choose2}-\sum_{s\inson}{2f_s+1\choose2}+f_x\]简单解释一下,\({f_x\ch......
  • [题解][洛谷P3584] LAS
    题目描述有n个蛋糕和n个人,每个蛋糕的热量是Ci。第i个人可以选择吃第i或第i+1个蛋糕,第n个人可以选择吃第n或第1个蛋糕。若一个蛋糕被两个人吃,那么每个人得到的热量是Ci/2.若一个人改变自己的选择,得到的热量增加,那么他会不满意。试输出让所有人满意的解,输出每个人吃蛋糕的序号......
  • Centos7 停止维护之后 升级gcc||找不到devtoolset-8-gcc* 问题解决方案
    为了去小米澎湃互联组,感觉必须得拿下linux网络编程,今天第一步这个centos就给我拉了坨大的问题实质SCL源没换,相信你也在别的教程上看到要安装centos-release-scl吧?有坑!安装完成后在/etc/yum.repos.d目录下会出现CentOS-SCLo-scl.repo和CentOS-SCLo-scl-rh.repo两个文件,......
  • [题解][洛谷P1578] 奶牛浴场
    题目描述在长宽为L,W的二维平面上有n个障碍点,试找到一个不覆盖任何障碍点(但点可以在边缘线上的)面积最大的矩形(长宽均与坐标轴平行)。输出面积。题意分析n的范围在5e3,考虑O(n2)的做法。易得面积最大的矩形四条边要么有障碍点,要么覆盖的边界。否则四条边可以继续扩展,面积会变得更......
  • [题解][洛谷P1633] 二进制
    题目描述有三个整数A,B,C,构造三个整数X,Y,Z满足:1.A,B,C在二进制下1的数量分别与X,Y,Z相等;2.X,Y,Z在二进制下的长度不超过A,B,C的最大长度;3.X+Y=Z。输出Z的最小值,若不存在Z,输出-1。题意分析首先考虑X,Y在什么情况下会使1的数量发生改变。设x,y,z分别表示X,Y,Z中1的数量,则......
  • CF542C题解
    传送门:https://codeforces.com/problemset/problem/542/C我们把序列的映射关系看作\(i\rightarrowf(i)\)的边,要使\(f(f(i))=f(i)\),显然存在\(i\)点距离不超过\(1\)的长度为\(1\)的自环。推广到\(f^{(k)}(x)\)满足题意则会在距离\(x\)点距离不超过\(k\)的长度为\(k\)的环。我们......
  • CF242D题解
    传送门:https://codeforces.com/problemset/problem/242/D对于一个点,显然一旦达到额定值后,其他任何操作都无法使他减小,于是我们得出一个贪心性质,当且仅当一个点不合法时,才取增加他的值。同理,我们可以证明,问题必定有解,因为若一个点被选择,必定是因为其曾不合法,选择后使其\(+1\)合法,......
  • CF549B题解
    传送门:https://codeforces.com/problemset/problem/549/B和CF242C思路完全相同,对于一个点,显然一旦达到额定值后,其他任何操作都无法使他减小,于是我们得出一个贪心性质,当且仅当一个点不合法时,才取增加他的值。同理,我们可以证明,问题必定有解,因为若一个点被选择,必定是因为其曾不合法,......
  • [题解]P7077 [CSP-S2020] 函数调用
    P7077[CSP-S2020]函数调用题意简述给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\),给定\(m\)个函数,每个函数可能是下面\(3\)种类型,用\(T_x\)表示函数\(x\)的类型:\(T_x=1\),对下标\(p\)增加\(v\)。\(T_x=2\),对所有元素乘\(v\)。\(T_x=3\),由若干类型\(1\)和类型\(2\)组成......