Rewinner

分类

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

/ 注册

全部文章（共136篇）

Power OJ 2826 有趣的游戏【Tanjar缩点+DAG最长路】

传送门 Description 一天wangshu迷上了一个十分有趣的游戏，名为sdfsfgdsfsdfsdfse，在在游戏里你需要从一个起始补给点开始去寻找装备，每一个补给点都有一定价值的装备，最后从出口补给点出去，这个游戏十分有趣，所以当你离开一个补给点后这个补给点会重生和原来一样...

2019-02-26

0 503

POJ 1904 King's Quest【Tanjar】

传送门 Description Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about ea...

2019-02-25

0 469

POJ 3228 Gold Transportation 【并查集】

传送门 Description Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this g...

2019-02-25

0 446

Proving Equivalences 【HDU-2767】强连通分量+Tanjar缩点

传送门题意：问至少增加多少有向边能将图变成强连通图？思路：如果存在强连通分量，那么我们可以将这个分量看作一个点（一个点也是强连通分量），利用tanjar缩点将原本复杂的图转化为多个DAG如何将这些DAG连接起来变成强连通图呢？ans=max(入度=0点的数量，出度=0点的数量) ///...

2019-02-24

0 419

POJ 3160 Father Christmas flymouse 【Tanjar缩点 + dfs】

传送门题意：给你一个有向图，找寻一条路径使得经过的权值和最大（点可以重复经过，但是权值只加一次，点上的权值可加可不加）。思路：用tanjar缩点将图转化为DAG，在tanjar缩点过程中记录一个强连通分量中正权值和，然后再跑一边记忆化dfs即可。 ///#include<bi...

2019-02-23

0 543

强连通图的算法【Tarjan】+ 【HDU1269】迷宫城堡

参考博客：https://blog.csdn.net/justlovetao/article/details/6673602 https://blog.csdn.net/qq_16234613/article/details/77431043 （代码含有注...

2019-02-23

0 721

Hdu 1350 Taxi Cab Scheme【最小边覆盖】

二分图：最小顶点覆盖=最大匹配最小边覆盖=顶点数-最小顶点覆盖（最大匹配）最小边覆盖：实质是个边集，这个集合里的边能覆盖所有的点，最小边覆盖是满足这个要求的所有边集中边数最少的一个。这里顶点数等于总的顶点数，是二分图两边的顶点数，不是一边。证明：设最大匹配数为m，总顶点数为n。为了使边...

2019-02-16

0 665

HDU 5040 Instrusive 【BFS+优先队列】

题意：你需要从M走到T，‘ # ’表示障碍不能走，‘ . ’表示道路，路上有W E N S的四种摄像头,每一秒钟会顺时针旋转一次，你拥有一个纸盒子（藏在纸盒子里不会被看到），你可以藏在纸盒子走需要花费3s，藏在纸盒子里原地不动1s，移动一步1s.到达T点所需要的时间。思路：很容易想到 bfs+...

2019-02-08

0 434

HDU 4639 离线树状数组

题目链接：传送门题意：给你一个 1—n 的排列，询问你区间 [ L,R ]中连续数的组数比如 1 4 3 5 6，就是3 （4 5 6一组，1 一组，3 一组）。 ///#include<bits/stdc++.h> ///#include<unordered_ma...

2019-01-25

0 471

【HDU 4348】 To the moon 可持久化线段树

题目链接：传送门简述题意：一个长度为n的数组，4种操作：　　　　（1）C l r d：区间[l,r]中的数都加1，同时当前的时间戳加1 。　　　　（2）Q l r：查询当前时间戳区间[l,r]中所有数的和。　　　　（3）H l r t：查询时间戳t区间[l,r]的和。　...

2019-01-25

0 595