Rewinner

分类

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章（共136篇）

差分约束建图【转载】

原博客：https://blog.csdn.net/qq_24451605/article/details/47121853 差分约束系统只是对最短路算法的一种应用，没有什么新的算法，只是对于具体问题的建图方法的确定 ---------------------------------------...

2019-03-05

0 491

欧拉图【模板+例题】

例题：UOJ 117 欧拉回路参考博客：https://www.cnblogs.com/Ash-ly/p/5397702.html （其中有向图的入度和出度好像写反了） https://blog.csdn.net/yzyyylx/article/details...

2019-03-04

0 568

曼哈顿最小生成树【模板题】

模板题：POJ 3241 曼哈顿最小生成树：给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。朴素的算法可以用O(N2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O(N2)条，所以Kruskal的复杂度变成了O(N2logN)。结论：以...

2019-03-03

0 949

POJ 1679 The Unique MST【次小生成树模板】

传送门 Description Given a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 (Spanning Tree): Consider a connected...

2019-03-02

0 445

康托展开与逆康托展开(转载)

一.引出康托展开动态规划题有一类分支叫状压DP，意思就是把状态压缩为一个二进制数组，然后转为十进制数存储。一般n的大小不会超过20，因为20个状态的组合就有2^20,也就是1e6种可能。对于一些题目，紧紧利用状态压缩，会发现状态的组合数远远超过1e6的范围，那时候我们没有办法在1s内...

2019-03-01

0 400

POJ 2449 Remmarguts' Date【A*算法 + 第K短路】

传送门 Description "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little duck...

2019-03-01

0 419

【LCA模板】Tanjar + 倍增LCA

Tanjar+并查集（离线查询）参考博客：https://www.cnblogs.com/jsawz/p/6723221.html #include<cstdio> #define N 420000 struct hehe{ int next; int to; ...

2019-02-28

0 516

A and B and Lecture Rooms CodeForces 519E 【LCA】

传送门 Description 在大学里，小A和小B是一对非常要好的朋友，他们经常一起参加比赛。现在，这个大学里有n个教室，这n个教室用n-1个走廊相互连接，因此学生可以从一个教室经过走廊走到任何其他的教室。每天，小A和小B都要讨论一些问题。每次下课以后（小A和小B在不同的地方上课），小...

2019-02-28

0 493

POJ 2763 Housewife Wind 【LCA】

传送门 Description After their royal wedding, Jiajia and Wind hid away in XX Village, to enjoy their ordinary happy life. People in XX Village lived in...

2019-02-27

0 584

ZOJ 3195 Design the city 【LCA】

传送门 Description Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams e...

2019-02-26

0 621