模拟赛题讲解[1]

来自 Roundgod 2022-07-25 noi.ac #2676

题目描述：

给定一个带权连通无向图 $G=(V,E)$ ，其中顶点个数 $|V|=n$ ，边数$|E|=m$ 图中可能包含重边以及自环。顶点编号为 $1−n$ ，边的编号为 $1−m$ ，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，权值为 $c_i$. 输入保证图中所有边的权值各不相同，即对于所有$1\le i<j \le n$ ，都有 $c_i\ne c_j$ 。

你现在需要处理 $q$ 个询问,其中第 $k$ 个询问是一个三元组 $(u_i,v_i,w_i)$ ，表示:

如果在图 $G$ 中添加一条连接 $u_i$ 和 $v_i$ 权值为 $w_i$ 的边得到图 $G^{\prime}$ ，图 $G^{\prime}$ 的最小生成树是否一定包含新添加的边?

询问保证对于所有 $1 \le j \le m$ ，都有 $w_i\ne c_j$ 。

输入格式：

输入第一行包含 $3$ 个整数 $n,m,q$ ，分别表示图的顶点数，图的边数，以及询问的个数。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,c_i(1\le a_i,b_i\le n)$ ，表示第 $i$ 条边连接的顶点以及权值。

接下来 $q$ 行，每行 $u_i,v_i,w_i(1\le u_i,v_i \le n)$ ，表示第 $i$ 组询问。

输出格式：

对于每组询问，根据答案你需要在一行中输出 Yes 或者 No

输入1：

输出1：

Yes
No
Yes

数据范围：

对于 $50\%$ 的数据，$1\le n \le 200,~1\le m \le 1000,~1\le q\le 1000,~1\le c_i,w_i \le 10^9$

对于 $100\%$的数据，$1\le n\le 2\times 10^5,~1\le m\le 2\times 10^5,~1\le q\le 2\times 10^5,~1\le c_i,w_i\le 10^{18}$

题解：

这个题还是蛮巧妙的

首先考虑 $q=1$ 的情况，

显然此时我们可以把这条边直接加进去跑一遍 $\text{kruskal}$

然后遇到这条边的时候，判断能否加入最小生成树

然后我们考虑 $q>1$ 的情况

最简单的想法是对于每个询问都跑一次，显然不可接受

仔细思考一下，就会发现，其实我们在判断的时候，

还是在原生成树的基础上尝试加入这条边的

而这个生成树是会把边一条一条从小到大加进去的

所以如果 $w_i$ 比较小，那么它会被先询问到

考虑离线处理所有询问，直接加入生成树去跑，然后只连原图的边

时间复杂度 $O((m+q) \log (m+q))$

数组别忘了开两倍哦~

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <set>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(5e5+15)

int n,m,Q,pos,f[N],r[N],ans[N];
set<int> s;
struct Edge{int u,v,w,id;} e[N];
bool operator<(Edge a,Edge b){return a.w<b.w;}
void init(int n){for(int i=1; i<=n; i++) f[i]=i,r[i]=0;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y)
{
    x=find(x); y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) f[x]=y;
    else f[y]=x,r[x]+=r[x]==r[y];
}
void kruskal()
{
    sort(e+1,e+1+pos); init(n);
    for(int i=1; i<=pos; i++)
    {
        if(e[i].id==-1)
        {
            if(find(e[i].u)!=find(e[i].v))
                merge(e[i].u,e[i].v);
        }else
        {
            if(find(e[i].u)!=find(e[i].v))
                ans[e[i].id]=1;
            else ans[e[i].id]=0;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m); read(Q);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u); read(v); read(w);
        s.insert(w); e[++pos]={u,v,w,-1};
    }
    for(int i=1,u,v,w; i<=Q; i++)
    {
        read(u); read(v); read(w);
        s.insert(w); e[++pos]={u,v,w,i};
    }
    kruskal();
    for(int i=1; i<=Q; i++)
        if(ans[i]) puts("Yes");
        else puts("No");
    return 0;
}