[BZOJ1579] [Usaco2009 Feb]Revamping Trails 道路升级（分层图最短路 + 堆优化dijk）传送门
dis[i][j]表示第i个点，更新了j次的最短路
此题不良心，卡spfa
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 50001
usi
[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门
蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs
[BZOJ1572] [Usaco2009 Open]工作安排Job（贪心 + 堆）传送门
把任务按照d排序
一次加入到堆中，如果当前放不进堆中，并且比堆中最小的大，
就从堆中弹出一个数，再把当前的数放进去
#include <queue>
#include <cstdio>
#include <
[luoguP2672] 推销员（贪心 + 树状数组 + 优先队列）传送门
贪心。。。蒟蒻证明不会。。。
每一次找最大的即可，找出一次最大的，数列会分为左右两边，左边用stl优先队列维护，右边用树状数组维护。。
（线段树超时了。。。。）
代码
[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）传送门
1.贪心 + 优先队列
按照时间排序从前往后
很简单不多说
——代码
1 #include <queue>
2 #include <cstdio>
3 #include <iostream>
4 #include <algorithm>
[luoguP2949] [USACO09OPEN]工作调度Work Scheduling（贪心 + 优先队列）传送门
这个题类似于建筑抢修。
先按照时间排序。
如果当前时间小于任务截止时间就选，
否则，看看当前任务价值是否比已选的任务的最小价值大，
如果是，就替换。
可以用优先队列
[luoguP1631] 序列合并（堆 || 优先队列）传送门
首先，把A和B两个序列分别从小到大排序，变成两个有序队列。这样，从A和B中各任取一个数相加得到N2个和，可以把这些和看成形成了n个有序表/队列：
A[1]+B[1] <= A[1]+B[2] <
[POJ3463] Sightseeing（次短路 Heap + Dijkstra）传送门
用dijkstra比较好，spfa可能有的重复
dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路；
tot[x][2]:tot[x][0]表示起点到x的最短路条数、tot[x
【模板】prim的heap优化简单的代码。。
时间复杂度为O((n + m)logn)
大部分情况下还是跑不过kruskal的，慎用。
1 #include <cstdio>
2 #include <queue>
3 #include <cstring>
4 #define hea
[HNOI2004]宠物收养场（Treap）
Treap——人和狗都收养
洛谷传送门
这题真是恶心，一开始没理解题意。
原来如果有狗，狗就会存在收养场中，直到有人来领养；
如果有人，人也会存在收养
【模板】Treap
Tree和Heap生了个孩子叫Treap
借鉴 模板 讲解
模板题
看了一上午才看明白，Treap = Tree + Heap，是棵弱平衡树。
一棵树同时具有二叉搜索树的性质和
Monkey King（左偏树）洛谷传送门
每次给出要争吵的猴子a和b，用并查集判断如果他们是朋友输出1
如果不是，找出a，b在的堆的根A，B，分别合并A，B的左右孩子，再合并一下。
之后把A，B的数据更改一下：权值除以2，左
【模板】左偏树洛谷模板题
一听左偏树这个名字就感觉左偏。。
左偏树是什么，好像就是个堆，大根堆或小根堆，可以支持合并，取堆顶元素，删除堆顶元素，插入元素的操作。
一些说明：
左偏树节点除了
【模板】Dijkstra的heap优化为了将最小费用最大流的spfa优化，决定将spfa换成heap优化的Dijkstra。（dijkstra不能处理负边权）
所以还得现学。。。
白点表示已经确定最短路径的点。
蓝点表示还未确定最短路
【模板】最小费用最大流洛谷模板题
没什么好说的，用spfa来找增广路。
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4
5 using namespace std;
6
7 const int
