5179: [Jsoi2011]任务调度
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5 Solved: 4
[Submit][Status][Discuss]
Description
一台超级计算机共有N颗CPU。现在这台超级计算机有M个任务要做，但同时还要考虑到不能让CPU过热。所幸的是这
台超级计算机已经将任务安排好了，现在要做的只是请你根据安排好的指令来模拟它的工作过程。一开始，这N颗C
PU都没有被分配任何的任务。之后，会给你以下几类指令（CPU的编号为1到N的整数，任务的编号为1到M的整数）
指令格式 作用
ADD n k w 将 k 号任务（权值为 w）分配给 n 号 CPU
DEC n k w 将 k 号任务的权值减少 w（已知 k 号任务被分配给了 n 号 CPU）
TRANS n1 n2 将分配给 n1 号 CPU 的任务全部转移给 n2 号 CPU
MIN n 输出分配给 n 号 CPU 的任务中权值最小的任务的权值
WORK n w 将分配给 n 号 CPU 的任务中权值最小的任务的权值加上 w，
如果权值最小的任务不唯一，则不更改权值，并输出一行“ ERROR”
Input
包含N+1行。
第1行包含三个正整数N、M、K，分别表示CPU的数目、任务数和指令数。
第2行到N+1行，每行包含一条指令。
N≤500， M≤300000， K≤300000。
保证任务的权值在 32 位有符号整型的范围内。
保证一个任务只会被分配一次（即至多被 ADD 一次）。
保证 ADD 指令、DEC 指令和 WORK 指令中的 w 是非负整数。
保证 TRANS 指令的两个参数不相同。
Output
若干行，其中包括MIN语句的输出和“ERROR”输出，每个输出占一行
Sample Input
2 3 13ADD 1 2 100ADD 1 1 90MIN 1WORK 1 20TRANS 1 2MIN 2ADD 1 3 105TRANS 2 1MIN 1DEC 1 3 200MIN 1DEC 1 1 205WORK 1 15
Sample Output
90100100-95ERROR
分析：
裸裸的可并堆题，用左偏树乱搞即可
代码：
# include <iostream># include <cstdio># include <algorithm>using namespace std;const int N = 3e5 + 12;int d[512],n,m,k;struct node{ ??int w,d,lc,rc,fa;}t[N];int merge(int x,int y){ ???if(!x)return y; ???if(!y)return x; ???if(t[x].w > t[y].w)swap(x,y); ???t[x].rc = merge(t[x].rc,y); ???t[t[x].rc].fa = x; ???if(t[t[x].rc].d > t[t[x].lc].d)swap(t[x].rc,t[x].lc); ???t[x].d = t[t[x].rc].d + 1; ???return x;}void erase(int x,int y,int z){ ???int u = merge(t[y].lc,t[y].rc),g = t[y].fa; ???if(d[x] == y)d[x] = u; ???if(t[g].lc == y)t[g].lc = u; ???else if(t[g].rc == y)t[g].rc = u; ???t[u].fa = g;t[y].lc = t[y].rc = t[y].fa = t[y].d = 0; ???t[y].w += z; ???d[x] = merge(d[x],y);}int main(){ ??scanf("%d %d %d",&n,&m,&k);char ch[5];int x,y,z; ??while(k--) ??{ ???scanf("%s",ch); ???if(ch[0] == ‘A‘) ???{ ???????scanf("%d %d %d",&x,&y,&z); ???????t[y].w = z; ???????d[x] = merge(d[x],y); ???} ???if(ch[0] == ‘D‘) ???{ ???????scanf("%d %d %d",&x,&y,&z); ???????erase(x,y,-z); ???} ???if(ch[0] == ‘T‘) ???{ ???????scanf("%d %d",&x,&y); ???????d[y] = merge(d[x],d[y]); ???????d[x] = 0; ???} ???if(ch[0] == ‘M‘) ???{ ???????scanf("%d",&x); ???????printf("%d\n",t[d[x]].w); ???} ???if(ch[0] == ‘W‘) ???{ ???????scanf("%d %d",&x,&y); ???????bool flag = true;int l = t[d[x]].lc,r = t[d[x]].rc; ???????if(l && t[l].w == t[d[x]].w)flag = false; ???????if(r && t[r].w == t[d[x]].w)flag = false; ???????if(flag)erase(x,d[x],y); ???????else puts("ERROR"); ???} ??}}[Bzoj5179][Jsoi2011]任务调度（左偏树）
原文地址：https://www.cnblogs.com/lzdhydzzh/p/8628252.html