2024牛客多校2B MST

Problem

Sajin最近深入研究了最小生成树，现在他已经掌握了MST的算法。他渴望通过一系列查询来评估您对最小生成树概念的掌握程度。

您将面临一个加权无向图，该图包含没有任何自环的 $n$ 个顶点和 $m$ 条边。

Sajin提出 $q$ 询问。对于每个顶点集，都给出了一个顶点集 $S$ 。您的目标是确定 $S$ 的诱导子图（induced subgraph）并找到其最小生成树的权重。如果 $S$ 的诱导子图断开，则输出-1。

图的诱导子图是另一个图，由图的顶点子集和原始图中的所有边组成，连接该子集中的顶点对。即，对于图 $G=(V,E)$ ，给定 $V^\prime$ ，则有 $E^\prime=\{(u,v) \mid u,v\in V^\prime,(u,v)\in E\}$，诱导子图为 $G^\prime=(V^\prime,E^\prime)$。

$2\le n\le 10^5,1\le m,q\le10^5$

$1 \le |S_i|\le n,\sum S_i\le 10^5$

Solution

Algorithm1

由于限制了 $\sum S_i\le 10^5$ ， MST本身的时间复杂度是完全过得去的。但是瓶颈在于如何从 $G$ 中挑出需要的边。

考虑两种找边的方法：

对于 $S$ 中的点 $x$，遍历 $x$ 的所有出边，终点为 $y$ 。如果 $y\in S$ ，那么边 $(x,y)\in G^\prime$ 。将得到的所有边存起来并排序跑kruskal。

对于一次询问，这个算法的最坏时间复杂度为 $O(m\log(|S|))$ ，即所有边都需要被遍历一次。

用map存图 $G$ ；双重遍历 $x,y\in S$ ，将其中存在的边 $(x,y)$ 取出来并排序跑kruskal。

整体时间复杂度是$O(n^2+n^2\log(n))$，即双重遍历和kruskal。

取 $base=\sqrt n$ ，

当 $|S|\le base$ 时使用第二种算法，总时间复杂度为 $O(n\cdot base\cdot \log(n))$
当 $|S| > base$ 时使用第一种算法，总时间复杂度为 $O(base\cdot m\cdot \log(n))$

Algorithm2

一般建立最小生成树，我们会使用上面的第一种找边的方式：对于 $S$ 中的点 $x$，遍历 $x$ 的所有出边，终点为 $y$ 。如果 $y\in S$ ，那么边 $(x,y)\in G^\prime$ 。将得到的所有边存起来并排序跑kruskal。

问题的瓶颈在于新建导出子图 $G^\prime$ 的时候，会被类菊花图卡掉。可能会一直询问类菊花图的核心点，而这些核心点具有很多条出边，每次询问都需要遍历核心节点的出边。

考虑类似三元环的连边方式，对于每条边，只从度小的点到度大的点连一条单向边。如果度数相同，则从编号小的连接到编号大的。

在这样构建的图中，每个点的出度不会大于 $\sqrt m$ 。如果有某个点的出度为 $d > \sqrt m$ ，那么在原图中，需要有 $d$ 个度数大于 $d$ 的节点与该节点连接，此时总边数至少 $d\times d>m$，矛盾。

所以可以在这样的一张单向图中放心的找边，单次询问时间复杂度 $O(|S| \sqrt m \log(|S|))$ 。

Code

Code1

#define N 100010
struct Edge
{
    int x,y;
    LL w;
    Edge(int xx,int yy,LL ww)
    {
        x=xx;
        y=yy;
        w=ww;
    }
    bool operator<(const Edge & z)
    {
        return w<z.w;
    }
};

int n,m,q;

namespace algo1{
    int cnt;
    int head[N],nxt[N*2],ver[N*2],w[N*2];
    void insert(int x,int y,LL z)
    {
        nxt[++cnt]=head[x];
        head[x]=cnt;
        ver[cnt]=y;
        w[cnt]=z;
    }
    
};

namespace algo2{
    map<pii,LL>mp;
    void insert(int x,int y,LL z)
    {
        pii e=make_pair(x,y);
        if(mp.find(e)==mp.end()) mp[e]=z;
        else mp[e]=min(mp[e],z);
    }
    bool exist(pii e)
    {
        return mp.find(e)!=mp.end();
    }
};

namespace DSU{
    int vis[N],f[N],sz[N];
    
    int getf(int x)
    {
        if(x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    
    void merge(int x,int y)
    {
        x=getf(x);
        y=getf(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        f[y]=x;
        sz[x]+=sz[y];
    }
    
    bool ask(int x,int y)
    {
        return getf(x)==getf(y);
    }
};

LL MST(vector<int>V,vector<Edge>E)
{
    sort(E.begin(),E.end());
    LL ans=0;
    int cnt=1;
    for(unsigned int i=0;i<E.size();i++)
    {
        if(!DSU::ask(E[i].x,E[i].y))
        {
            cnt++;
            DSU::merge(E[i].x,E[i].y);
            ans+=E[i].w;
        }
    }
    if(cnt!=V.size()) return -1;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//    cin>>t;
    while(t--)
    {
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            LL z;
            cin>>x>>y>>z;
            algo1::insert(x,y,z);
            algo1::insert(y,x,z);
            algo2::insert(x,y,z);
            algo2::insert(y,x,z);
        }
        const int base=sqrt(100000);
        while(q--)
        {
            int k;
            cin>>k;
            vector<int>S;
            vector<Edge>E;
            for(int i=0;i<k;i++)
            {
                int t;cin>>t;
                S.push_back(t);
                DSU::vis[t]=1;
                DSU::sz[t]=1;
                DSU::f[t]=t;
            }
            if(k>base)
            {
                //algo1
                for(int i=0;i<k;i++)
                {
                    int x=S[i];
                    for(int j=algo1::head[x];j;j=algo1::nxt[j])
                    {
                        int y=algo1::ver[j];
                        LL w=algo1::w[j];
                        if(DSU::vis[y])
                        {
                            E.push_back(Edge(x,y,w));
                        }
                    }
                }
            }
            else
            {
                //algo2
                for(int i=0;i<k;i++)
                {
                    for(int j=i+1;j<k;j++)
                    {
                        pii e=make_pair(S[i],S[j]);
                        if(algo2::exist(e))
                        {
                            E.push_back(Edge(S[i],S[j],algo2::mp[e]));
                        }
                    }
                }
            }
            
            cout<<MST(S,E)<<endl;
            
            for(int i=0;i<k;i++)
            {
                DSU::vis[S[i]]=0;
            }
        }
    }
    return 0;
}

生最差劲的一件事莫过于早上写的代码但半路跑路还没做任何标记，晚上打开不知道从何续写。

人生最美好的一件事莫过于发现这份代码其实是以及写完的！？而且还能过样例！？？而且直接提交直接过了！？？？

Code2

#define N 100010
struct Edge
{
    int x,y;
    LL w;
    Edge(int xx,int yy,LL ww)
    {
        x=xx;
        y=yy;
        w=ww;
    }
    bool operator<(const Edge & z)
    {
        return w<z.w;
    }
};

int n,m,q;


namespace G1
{
    map<pii,LL>mp;
    int degree[N];
    void insert(int x,int y,LL z)
    {
        pii e=make_pair(x,y);
        if(mp.find(e)==mp.end()) mp[e]=z;
        else mp[e]=min(mp[e],z);
        degree[x]++;
    }
};

namespace G2
{
    int cnt;
    int head[N],nxt[N*2],ver[N*2];
    LL w[N];
    void insert(int x,int y,LL z)
    {
        nxt[++cnt]=head[x];
        head[x]=cnt;
        ver[cnt]=y;
        w[cnt]=z;
    }
};

namespace DSU{
    int vis[N],f[N],sz[N];
    
    int getf(int x)
    {
        if(x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    
    void merge(int x,int y)
    {
        x=getf(x);
        y=getf(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        f[y]=x;
        sz[x]+=sz[y];
    }
    
    bool ask(int x,int y)
    {
        return getf(x)==getf(y);
    }
};


LL MST(vector<int>V,vector<Edge>E)
{
    sort(E.begin(),E.end());
    LL ans=0;
    int cnt=1;
    for(unsigned int i=0;i<E.size();i++)
    {
        if(!DSU::ask(E[i].x,E[i].y))
        {
            cnt++;
            DSU::merge(E[i].x,E[i].y);
            ans+=E[i].w;
        }
    }
    if(cnt!=V.size()) return -1;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//    cin>>t;
    while(t--)
    {
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            LL z;
            cin>>x>>y>>z;
            G1::insert(x,y,z);
            G1::insert(y,x,z);
        }
        
        for(auto it=G1::mp.begin();it!=G1::mp.end();it++)
        {
            int x=it->first.first,y=it->first.second;
            LL w=it->second;
            if(G1::degree[x]<G1::degree[y]||(G1::degree[x]==G1::degree[y]&&x<y)) G2::insert(x,y,w);
        }
        
        while(q--)
        {
            int k;
            cin>>k;
            vector<int>S;
            vector<Edge>E;
            for(int i=0;i<k;i++)
            {
                int t;cin>>t;
                S.push_back(t);
                DSU::vis[t]=1;
                DSU::sz[t]=1;
                DSU::f[t]=t;
            }
            for(int i=0;i<k;i++)
            {
                int x=S[i];
                for(int j=G2::head[x];j;j=G2::nxt[j])
                {
                    int y=G2::ver[j];
                    LL w=G2::w[j];
                    if(DSU::vis[y])
                    {
                        E.push_back(Edge(x,y,w));
                    }
                }
            }
            
            cout<<MST(S,E)<<endl;
            
            for(int i=0;i<k;i++)
            {
                DSU::vis[S[i]]=0;
            }
        }
        
        
    }
    return 0;
}

← BACK TO INDEX NOTE / 2024—07

本文作者：Vanilla

本文链接：https://vanilla-chan.cn/blog/2024/07/20/2024%E7%89%9B%E5%AE%A2%E5%A4%9A%E6%A0%A12B-MST/

#2024ACM #三元环 #分治 #MST #DSU

COMMENTS

via giscus