如果$x_j,y_j$在不同的并查集,那么我们必须介绍这两个并查集中的人互相认识,那么我们尽量把所有人都介绍给同一个人认识,这样就能满足某个人认识的人最多,而这个人数的数量,其实就是这个并查集的大小
如果$x_j,y_j$已经在不同的并查集里了,那么说明我们可以任意介绍两个人,为了满足某个人认识的人最多,那么我们肯定是合并两个最大的并查集。

具体做法

对于每一次回答,我们重新计算并查集,顺带算出可以任意合并次数,然后按照并查集大小,依次合并,计算答案。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 1e4 + 7;

int n, m, fa[maxN], siz[maxN], e[maxN][2], num[maxN];

int Find(int x)
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

bool cmp(int x, int y)
{
    return siz[x] > siz[y];
}

int main()
{
    scanf("%d%d", &n, &m);
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        for(int i = 1; i <= n; ++i) {
            fa[i] = i;
            siz[i] = 1;
            num[i] = i;
        }
        scanf("%d%d", &e[i][0], &e[i][1]);
        int cnt = 0, mx = 0;
        for(int j = 1; j <= i; ++j) {
            int fx = Find(e[j][0]), fy = Find(e[j][1]);
            if(fx != fy) {
                fa[fy] = fx;
                siz[fx] += siz[fy];
                if(siz[fx] > siz[mx])
                    mx = fx; //记录最大的并查集编号
            }
            else
                ++cnt;
        }
        sort(num + 1, num + 1 + n, cmp); //num数组的值就是并查集编号,num[1]表示就是最大的并查集编号
        for(int i = 1; i <= n && cnt; ++i) {
            int fz = Find(num[i]);
            if(fz == mx)
                continue;
            fa[fz] = mx;
            siz[mx] += siz[fz];
            cnt--;
        }
        printf("%d\n", siz[mx] - 1);
    }
    return 0;
}

展开全文 >>

Life is a Game

2021-12-06

题目大意

给定一个$n$个节点和$m$条边($u,v,w$)的图,有$q$次询问($x,k$)($1 \le n,m,q \le 10^5$),

每次询问为以下含义:

你最开始在$x$节点,有$k$点能力值,每次第一次到一个节点$i$,就能获得$a[i]$点能力值(最开始当然也会获得$x$节点的能力值)

而通过每一条边需要有最少有$w_i$的能力值，通过边不会减少能力值,

可以多次经过同一个点和边,求你最后的能力值最多为多少。
原题地址

more >>

展开全文 >>

KruskalTree

2021-12-04

适用场合

多次询问在一个图中,两个点之间的最短路上的最长边。这个题有多种解法,用$Kruskal$重构树的方法当然也能解决。

主要思想

建一个新的树 * 按照Kruskal算法依次遍历边,当要进行合并时,再执行以下操作

把最小生成树上的边$(u,v,w)$当作新的点,权值为原来边权$w$
分别两条边连向$u$,$v$所在的子树的根节点

求两个点$x,y$之间最短路上的最长边,等价于在新的树上$LCA(x,y)$的权值。

这里本来应该有个图,但是出于申必原因加载不出来,可以来CSDN上康康

代码

这个是用来解决货车运输的代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxN = 1e5 + 7;

int n, m, q, cnt, head[maxN], fa[maxN], tot, val[maxN], f[maxN][21], depth[maxN];

struct Edge {
    int from, to, dis;
}e[maxN << 1], initEdge[maxN];

inline void add(int u, int v)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}

int Find(int x)
{
    return fa[x] == x? x : fa[x] = Find(fa[x]);
}

bool cmp(Edge x, Edge y)
{
    return x.dis > y.dis;
}

void dfs(int x)
{
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        f[y][0] = x; depth[y] = depth[x] + 1;
        dfs(y);
    }
}

inline void KruskalTree()
{
    sort(initEdge + 1, initEdge + 1 + m, cmp);
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    tot = n; //tot记录的是新的图上点的个数   
    for(int i = 1; i <= m; ++i) {
        int fx = Find(initEdge[i].from), fy = Find(initEdge[i].to);
        if(fx == fy)
            continue;
        val[++tot] = initEdge[i].dis; //建立新的树
        fa[tot] = fa[fx] = fa[fy] = tot;
        add(tot, fx); add(tot, fy);
    }
}

inline void initLca() //从这开始就是普通的LCA了
{
    for(int i = tot; i >= 0; --i) 
        if(!depth[i])
            dfs(i);
    for(int j = 1; (1 << j) <= tot; ++j)
        for(int i = 1; i <= tot; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
}

int Lca(int x, int y)
{
    if(depth[x] < depth[y])
        swap(x, y);
    int t = (int)(log(depth[x]) / log(2)) + 1;
    for(int i = t; i >= 0; i--)
        if(depth[f[x][i]] >= depth[y])
            x = f[x][i];
    if(x == y)
        return x;
    for(int i = t; i >= 0; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];             
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d", &initEdge[i].from, &initEdge[i].to, &initEdge[i].dis);
    KruskalTree();
    initLca();
    scanf("%d", &q);
    while(q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if(Find(x) != Find(y)) //当然图可能不连通
            printf("-1\n");
        else
            printf("%d\n", val[Lca(x, y)]);    
    }
    return 0;
}

展开全文 >>

Edge groups

2021-12-02

题目大意

给定一张$n(3\le n \le 10^5)$个节点的树($n$为奇数),将这$n-1$条边两两分组,

要求:分到同一组的边有相同的顶点。

求一共有多少种方法。结果对$998244353$取模

more >>

展开全文 >>