严格次小生成树

题意简述给定一个无向连通图,求出它的一棵生成树,满足边权之和仅次于最小生成树。 解题思路一个很自然的想法就是,枚举每一条选中的边,用另外一条没选中的边替换,求出次小值。 考虑怎么优化这个算法。 ...

严格次短路

题意简述给定一张无向联通图,求一条 1 到 n 的路径使得它的长度仅次于最短路。 解题思路其实这个和最短路差不多,无非就是 BFS 的时候再维护一个次短路数组 dist[u][1] 表示 1 点...

如何把 Android P 的小药丸改成 Q 的小横条

Android Q 是真的香,可惜我只有 Android P 前言看了酷安上一条动态,上面说 Android P 可以获得 Q 的动画和手势,我当即就备份好数据刷了 OmniROM Pi...

洛谷P1608《路径统计》

《最短路计数》加上一点小细节 解析具体实现思想就不说了。说一点要注意的细节: 判重!!! 本题有重边,而且重边似乎不算不同路径? 所以要对本题的加边稍加修改 1234567891011i...

POJ2001《Shortest Prefixes》

这题在纸上手玩一遍找找规律就出来了 传送门:http://poj.org/problem… 解析首先看到这是个字符串题 再然后一想,这个要处理前缀相等问题 好,就是你了,Trie 先把...

洛谷P2761《软件补丁问题》

或 CTSC99《补丁 VS 错误》 说的那么麻烦,其实就一最短路。。 题目传送门:https://www.luogu.com.cn/problem/P2761 解析第一个,这题是状压,...

洛谷P2449《[SDOI2005]矩形》

真就正解是暴力呗 题目描述现在我们在一个平面上画了n个矩形。每一个矩形的两边都与坐标轴相平行,且矩形定点的坐标均为整数。现我们定义满足如下性质的图形为一个块: 1.每一个矩形都是一个块;...

洛谷P3200《[HNOI2009]有趣的数列》

卡特兰数 + 质因数分解 题目描述我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件: (1)它是从1到2n共2n个整数的一个排列{ai}; (2)所有的奇数项满足a1&...

BZOJ3331《[BeiJing2013]压力》

题意给你一张 n 个点 m 条边的无向图,再给你 q 个点对,让你计算对于每一个点,有多少个点对间的路径必定经过这个点。N≤100000,M,Q≤200000。 解析首先可以发现这样一个东西...

1234520