1. 题目

传送门= ̄ω ̄=

2. 题解

MMP明天期末考啊

我已经准备好裸考了

做法1

优先队列(二叉堆)的启发式合并。

合并两个堆的时候把元素个数较少的堆中的元素一个一个丢到元素较多的堆中。

用并查集维护某个元素所在的堆的编号。

复杂度$O(nlog_2n)$

代码:

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
typedef pair<int,int> PII;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,fa[NS];
bool book[NS];
priority_queue<PII,vector<PII>,greater<PII> > pq[NS];
int findf(int a){return fa[a]==a?a:fa[a]=findf(fa[a]);}
int main()
{
    IN(n),IN(m);
    for(int i=1,j;i<=n;i++)IN(j),pq[i].push((PII){j,i}),fa[i]=i;
    for(int i=1,a,b,c;i<=m;i++)
        if(IN(a),IN(b),a==1)
        {
            if(IN(c),book[b]||book[c])continue;
            b=findf(b),c=findf(c);
            if(b==c)continue;
            if(pq[b].size()>pq[c].size())swap(b,c);
            while(!pq[b].empty())
            {
                pq[c].push(pq[b].top());
                fa[pq[b].top().second]=c;
                pq[b].pop();
            }
        }
        else
        {
            if(book[b]){puts("-1");continue;}
            b=findf(b),printf("%d\n",pq[b].top().first);
            book[pq[b].top().second]=1,pq[b].pop();
        }
    return 0;
}

做法2

左偏树。

复杂度$O(nlog_2n)$

注意这个代码里的$f$不是并查集而是左偏树中节点的父节点。

$findf$指的是求某节点所在的左偏树中的根节点编号

代码:

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
typedef pair<int,int> PII;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{PII d;int l,r,dis,f;}e[NS];
int n,m;
bool book[NS];
int findf(int a){return e[a].f?findf(e[a].f):a;}
int merge(int a,int b)
{
    if(!a)return b;if(!b)return a;
    if(e[a].d>e[b].d)swap(a,b);
    e[a].r=merge(e[a].r,b),e[e[a].r].f=a;
    if(e[e[a].r].dis>e[e[a].l].dis)swap(e[a].l,e[a].r);
    e[a].dis=e[e[a].r].dis+1;
    return a;
}
int main()
{
    IN(n),IN(m);
    for(int i=1,j;i<=n;i++)IN(j),e[i].d=(PII){j,i};
    for(int i=1,a,b,c;i<=m;i++)
        if(IN(a),IN(b),a==1)
        {
            if(IN(c),book[b]||book[c])continue;
            b=findf(b),c=findf(c);
            if(b!=c)merge(b,c);
        }
        else
        {
            if(book[b]){puts("-1");continue;}
            b=findf(b),printf("%d\n",e[b].d.first);
            book[e[b].d.second]=1;
            e[e[b].l].f=e[e[b].r].f=0,merge(e[b].l,e[b].r);
        }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *