已注销

图论

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / 图论（共96篇）

HDU-1829-A Bug's Life

ACM模版描述题解种类并查集，相邻的两个关系如果是同性，则冲突（也就是gay），否则，正常。代码 #include <stdio.h> const int MAXN = 2010; int pre[MAXN]; int rank[MAXN]; // 1:同 0...

2021-05-21

0 311

HDU-1558-Segment set

ACM模版描述题解计算几何+并查集。神奇的组合…… 代码 #include <iostream> const double eps = 1e-10; const int MAXN = 1010; struct point { double x, y; };...

2021-05-21

0 300

HDU-2473-Junk-Mail Filter

ACM模版描述题解并查集+设立虚父节点(马甲)，第一眼看，是不是很懵逼？马甲？what’s this? 第一次做这种并查集，看了题解（源码）后，顿悟，pre[]不再是够n就行了，而需要留出拓展的空间，通过对虚父节点的操作来不断扩展并查集，就像给他套了一层马甲一般，而这个马甲pre_...

2021-05-21

0 390

HDU-3635-Dragon Balls

ACM模版描述题解让悟空学学并查集就搞定了~~~ 这里的两种操作需要说一下，翻译起来好难。 T A B把A龙珠所在城市的所有龙珠都移到B龙珠所在城市； Q A查询A龙珠相关信息，分别是A龙珠现在所在城市、该城市的龙珠数目、A转移到该城市所移动的次数。代码 #include...

2021-05-21

0 423

HDU-3047-Zjnu Stadium

ACM模版描述题解带权并查集，题真难读。代码 #include <cstdio> #include <cmath> using namespace std; const int MAXN = 50005; int n, m; int pre[MAX...

2021-05-21

0 325

HDU-3038-How Many Answers Are Wrong

ACM模版描述题解有人说这道题是种类并查集，可能是我的概念不好吧，带权并查集搞搞就行了，和HDU 3047 Zjnu Stadium几乎代码一模一样，不同的是，这个题的思路容易跑偏，可能会想到线段树（毕竟和区间挂钩了），但是，并查集搞搞就KO了…… 代码 #include <...

2021-05-21

0 0

HDU-2818-Building Block

ACM模版描述题解并查集搞搞，这里是带权并查集，需要加一个low[]来记录结果，需要格外注意的是最后输出语前的那句find()，看似没有啥用，但是十分有必要，因为需要通过他来更新low[]的值。代码 #include <iostream> #include <...

2021-05-21

0 371

HDU-2121-Ice_cream’s world II

ACM模版描述题解朱刘算法，最小树形图，第一次做这个算法的题，感觉自己无知迷茫的眼神好萌，目前大致理解了原理，可是还停留在套模版的水平……甚至，连模版都套不好，/(ㄒoㄒ)/~~ 代码 #include <iostream> #include <cstring&...

2021-05-21

0 308

HDU-4009-Transfer water

ACM模版描述题解最小树形图，模版题，之所以这么说有两个原因，第一，真的是模版，第二，我只会套模版，增加超级源点搞搞。如果有比较好的最小树形图的算法资料，欢迎推荐~~~ 代码 #include <iostream> #include <cmath> #...

2021-05-21

0 393

HDU-2586-How far away ？

ACM模版描述题解由于英语不好，猛一看，以为是最短路，然后发现，竟然有这么多次查询，所以果断想到了LCA，求最近公共祖先。求最近公共祖先，方法很多，主要分为离线和在线两种，离线算法比较好的是Tarjan算法，在线比较好的是ST算法，这里使用ST算法搞搞事情。定义一个dir[]数组在d...

2021-05-21

0 478