poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。 然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。 /* *********************************************** Author :111qqz Created Time :2016年07月13日 星期三 19时53分29秒 File Name :code/poj/1751.cpp ************************************************ */ #include …

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候，答案为k-1,否则答案为d+(k-d-1)*2。。。 因 …

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过 环的话并查集就好。。 关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？ 于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。 具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一 …

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 16时16分52秒 File Name :code/poj/1679.cpp ************************************************ */ #include <cstdio> #include <cstring> …

hdu4514 题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。 思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。 但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。 也就是要在一个不联通的图中求最长路径。。。 没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。 不过感觉最容易想到的还是求多次直径的做法。。。 也就是。。每一个联通块求一次直径。。。取最大。。。 具体做的时候。。。加一个bool数组在bfs标记一下就好。。。 以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注 …

hdu2196 题意：给出一棵树。。。求距离每个点的最远距离是多少。。。 思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？ 1A. /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时29分49秒 File Name :code/hdu/2196.cpp …

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时03分39秒 File Name :code/poj/2631.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。 思路： **两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；** 原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点 证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度 参考博客 实际写的时候，第一次bfs最后一个出 …

* <del>树的直径，次小生成树（）</del> * <del>最小生成树（拒绝划水，推一波难题）</del> * 《编程珠玑》 * 博弈论。。全部搞定。。。 * dp。。。基础dp，区间dp，树形dp，概率dp。。至少搞定这些。。（从头开始学dp2333） * <del>markdown语法。。还是有必要学一下的。</del> * <del>multi 2016 #4 1006 -> SA SA? SA SA!</del> * <del>单调栈？单调栈？单调栈单调栈！ （一堆题卡在这里 …

URAL1416 题意：次小生成树模板题 思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。 写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz... /* *********************************************** Author :111qqz Created Time :2016年07月11日 星期一 20时44分28秒 File Name …