题意给一个 $N\times N$ 网格图，汽车从 $(1,1)$ 走到 $(N,N)$ 。网格图中有加油站，汽车到了加油站就会被强制加油花费 $A$ ；如果没油了也可以设立一个油库并加油，花费 $C+A$ ；如果往回走（ $X,Y$ 坐标有一个减小）会花费 $B$ 。汽车邮箱容量为 $K$ ，每走一条边消耗 $1$ 单位的油。求花费的最小值。题解朴素的 $bfs$ 就可以过，不过会成为反向...
题意给出一个有向图，需要从 $1$ 走到 $N$ ，可以在一个城市买水晶球并在另一个城市卖掉，也可以不买，问最多能赚多少钱。其中 点数$n\le 100000$ ，边数$m\le 500000$ 。题解分层图最短路。对于原图，买卖操作各建一层图，边权为在起点买卖水晶球的花费（买为负卖为正）。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ，对于每...
题意有一个 $N\times M$ 的长方形迷宫，相邻两个单元之间可能有不能通过的墙或可以用第 $Q_i$ 种钥匙打开的门，有的单元中有第 $Q_i$ 种钥匙。从 $(1,1)$ 出发，目标是 $(N,M)$，每次只能移动一个单元，求最短移动时间。其中 $N,M\le 10$ ，钥匙的种类数 $P\le 10$ 。题解钥匙的种类数不多，考虑直接状压搜索。用 $s[x][y][i]$ 表示 $...
题意有一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。题解我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树，再对黑边跑剩下的就行了。但打到一半突然发现不行，于是便跑去看题解。显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小，那么我们就可以给所有白边加一个权值 $x$ 然后再跑；如果白边少了同理。...
题意求无向图最小环，要求输出路径。其中点数 $N\le 100$题解本来求最小环挺简单的，恶心的就是这道题还要求输出路径。求最小环的方法就是用 $spfa$ 跑最短路，得到最初的距离 $dis[u][v]$ 和最短路 $mn[u][v]$ 。那么对于每个节点 $x$ ，它与 $u$ 和 $v$ 相邻，那么他们最小环的长度即为：$$mn[u][v]+dis[x][u]+dis[x][v]$$每...
题意给一个无向图，求严格次小最短路。其中点数 $N\le 5000$ ，边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较，将较小值给最短路，较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重，可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
题意求 从$1$ 到 $N$ 的一条路径，使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ，边数 $P\le 2000$，权值 $L_i\le 10^{6}$题解直接求肯定没有办法，所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分，每次检验就跑一次 $Dijkstra$ ，只是把边权变为 $>x$ 的边的条数，这样就可以得到$>x$ 的边最少...
题意给一个无向简单图，求最小生成树的个数，对 $31011$ 取模。其中点数 $n\le 100$ ，边数 $m\le 1000$ 。题解有个性质：在不同的最小生成树中，每种权值的边的数量一定相同。这道题又有个限制：具有相同权值的边不会超过 $10$ 条，那么就可以直接用那个性质来暴力了。先跑出来最小生成树，记录下来每种权值的边的数量 $t\_cnt[]$ 以及每种权值的起始位置 $l[]$...
因为NOIp考爆本来不想去的，然后被建军和徐妈威逼利诱去了，于是还是来划水了。Day1说是 $9$ 点到 $12$ 点报道，然后徐妈觉得是 $9$ 点之前，然后我们一行在早高峰挤地铁那滋味真酸爽，关键是还没吃早饭，直到 $10$ 点报完到才吃。中午点了开封菜的外卖就开始颓废，话说还有一盒土豆泥和一个鸡腿没吃完，太可惜了。下午去水笔试，看了下资料，纯凭感觉，说是考 $1h$ 事实上 $10 m...
图文无关出道裸题觉得简单了非要上树系列。如果没在树上就是裸的可持久化字典树，在树上写个树剖就完事了。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')...