首页 > 代码库 > [BZOJ 1455]罗马游戏（左偏树+并查集）
[BZOJ 1455]罗马游戏（左偏树+并查集）
Description
罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令： 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。 皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）
Solution
比较裸的一道左偏树
#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#define MAXN 1000005using namespace std;int n,m,father[MAXN];bool die[MAXN];struct Node{ int lch,rch,w,d; Node():lch(0),rch(0),w(0),d(0){}}heap[MAXN];int merge(int x,int y){ if(!x||!y)return x+y; if(heap[x].w>heap[y].w)swap(x,y); heap[x].rch=merge(y,heap[x].rch); if(heap[heap[x].lch].d<heap[heap[x].rch].d)swap(heap[x].lch,heap[x].rch); heap[x].d=heap[heap[x].rch].d+1; return x;}int find(int x){ if(x==father[x])return x; return father[x]=find(father[x]);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&heap[i].w); father[i]=i;} scanf("%d",&m); for(int i=1;i<=m;i++) { char opt[3];int x,y; scanf("%s",opt); if(opt[0]==‘M‘) { scanf("%d%d",&x,&y); if(die[x]||die[y])continue; int fx=find(x),fy=find(y); if(fx!=fy) father[fx]=father[fy]=merge(fx,fy); } else { scanf("%d",&x); if(die[x])printf("0\n"); else { int fx=find(x); die[fx]=1; printf("%d\n",heap[fx].w); father[fx]=merge(heap[fx].lch,heap[fx].rch); father[father[fx]]=father[fx]; } } } return 0;}
[BZOJ 1455]罗马游戏（左偏树+并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。