[ABC302F] Merge Set 题解

· · 题解

Part 1: 分析求解

套路建图题，读完题不难可以构造出一个二分图，左边是每个集合，称为集合点，右边是 1-m，称为数字点；

而题目要求的是一个集合包含 1 和 m 的最少操作步数。

一次操作中使用的两个集合相当于从第一个集合点到其中的一个数字点再到第二个集合点，代价为 1，而我们拥有的集合可以走向任意在集合中的数字点且代价为 0。

所以我们只需要将每一个集合点连向相匹配的数字点，代价为 0，将每一个数字点连向相匹配的集合点，代价为 1，跑跑最短路就好了。

Part 2: CODE

//#pragma GCC optimize(3)
#include<iostream>
#include<climits>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<assert.h>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
//#include<random>
//#include<chrono>
#define int long long
//#define double long double
using namespace std;
const long long INF=LLONG_MAX/2ll;
const long long mod=998244353;
//const long long mod=1000000007;
const double Pai=acos(-1);
const double eps=1e-8;
int n,m,cnt=0;
int dis[1000005],h[1000005],vst[1000005];
struct edge {
    int to,next,v;
}e[1000005];
void addedge(int x,int y,int z) {
    cnt++;
    e[cnt].to=y;
    e[cnt].v=z;
    e[cnt].next=h[x];
    h[x]=cnt;
}
priority_queue< pair<int,int> > q;
void Dij(int s) {
    for(int i=1;i<=n+m;i++) dis[i]=INF,vst[i]=0;
    dis[s]=0,q.push({-dis[s],s});
    while(!q.empty()) {
        int u=q.top().second;q.pop();
        if(vst[u]) continue;
        vst[u]=1;
        for(int i=h[u];i;i=e[i].next) {
            int y=e[i].to;
            if(dis[y]>dis[u]+e[i].v) {
                dis[y]=dis[u]+e[i].v;
                q.push({-dis[y],y});
            }
        }
    }
}
signed main() {
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) {
        int x;scanf("%lld",&x);
        for(int j=1;j<=x;j++) {
            int y;scanf("%lld",&y);
            addedge(i+m,y,0),addedge(y,i+m,1);
        }
    }
    Dij(1);
    if(dis[m]==INF) puts("-1");
    else printf("%lld",dis[m]-1);
    return 0;
}