ABC235E MST+1 题解

题目大意

给你一个图 \(G\) 含有 \(n\) 个顶点和 \(m\) 条边，给出 \(Q\) 次询问，询问所多输入的边加上原图 \(G\) 的最小生成树是否是存在 \(e_i\)，存在输出 Yes 不存在输出 No。

思路

首先我们可以想到用最简单的方法，在每次询问时都做一次 Kruskal 算法，如果这个边被取到了，那么输出 Yes，反之亦然。时间复杂度为 \(\mathcal{O}(Q \times n \log n)\)，太慢。

因为每个询问是相互独立的，而且询问的边 \(e_i\) 对于 并查集 的不会产生影响，所以可以想到只用一次 Kruskal 算法，把所有的边都涵盖上。

在遍历时每条边的处理方法：

• 如果是询问的 \(e_i\) 的边

  • 如果 \(e_i\) 的所连的两个顶点 \(u,v\) 没有连通，则标记为 Yes。

  • 如果连通，则标记为 No。

• 如果是询问的 \(e_i\) 的边

  • 如果 \(e_i\) 的所连的两个顶点 \(u,v\) 没有连通，则标记为 Yes。

  • 如果连通，则标记为 No。

• 如果是 \(G\) 的边        

  • 将两个顶点在并查集内合并

时间复杂度 \(\mathcal{O}((n+Q) \log (n + Q))\)。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int maxn = 200005;

struct Edge{int u,v,w,Is,num;};
int fa[maxn];
Edge e[maxn*2];
bool ans[maxn];
int n,m,q;
vector<Edge> qe;

bool operator ==(const Edge &a,const Edge &b){return (a.u == b.u && a.v == b.v && a.w == b.w);}

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


bool cmp(Edge x,Edge y){
    return x.w < y.w;
}

inline void Init_Onion(){
    for(int x=1;x<=n;x++)    fa[x] = x;
    memset(ans,0,sizeof(ans));
}


int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
        e[i].Is = 0;
    }

    for(int i=1;i<=q;i++){
        scanf("%d %d %d",&e[m+i].u,&e[m+i].v,&e[m+i].w);
        e[m+i].Is = 1;e[m+i].num = i;
    }

    sort(e+1,e+m+q+1,cmp);
    Init_Onion();

    int k = 0;
    for(int i=1;i<=m+q;i++){
        if(e[i].Is == 1){
            if(found(e[i].v) != found(e[i].u))
                ans[e[i].num] = 1;
            continue;
        }

        int u = e[i].u,v = e[i].v;
        int f = found(u),t = found(v);
        fa[t] = f;
    }

    for(int i=1;i<=q;i++){
        if(ans[i] == 1)
            printf("Yes\n");
        else
            printf("No\n");#191B1C
    }    
    return 0;
}