思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
https://cn.vjudge.net/problem/SGU-206
这个题乍一看不可做系列(难道不是吗)，像是跟生成树相关的问题。然而看了dalao的博客和论文之后总算搞明白了原来要转化为二分图模型。而之所以能转化就是因为里面的绝对值去掉不等式（去绝对值用的是贪心的思想，1-n-1之间的都要变小，n到m的都要变大）之后，非树边 j 和树边 i 的delta关系可以写成Di+Dj>=Ci-Cj,然后dalao们就想到了KM算法里的标杆与权值之间的不等式关系 鬼知道他们怎么想到的 继续阅读“[二分图带权匹配][KM算法][图论][模型转化] SGU 206 Roads”
这个题确实是领悟到了不少东西，lca倍增的思想和用途，思维方法，构建生成树的逻辑，严格次小的要求。发现图论很重要的一个东西就是存储用的数据结构，我不怎么会写前向星于是就很难受了。。就这个题而言是要先求MST，再对MST做LCA，那么就会有两个图，一个是原始的用来求MST，另一个用来求LCA，第二个就是MST这个树本身。所以建了俩图，第二个图是在Kruskal的过程中建立的，与此同时还要记录下来不在MST上的边，以便之后的枚举操作。另外一个需要注意的点就是要求是严格次小，所以的就需要保存一个第二大这么一个数，这个又有很多情况，不同树上区间合并的时候根据两个区间最大的数的关系来处理。
错误的话，1 求LCA的时候应该swap 使得较深的为y，这里写错了 2 数组容量开错，这个今天错了几次，主要是没看清m和n，而且总是蜜汁把m写成n。。 3 数组下标写错（为什么经常做这种蠢事？？？？ 4 跟LL比较大小却初始化为1<<29，，显然不够，改成1<<60就过了，也是最后一个错误
继续阅读“[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题”
扯淡的就是我们队训练赛两个队友一个过了一个一人题一个过了一个5人题，然后我这边有两个通过率90%+的卡住没过，呵呵了真的是，怀疑人生。
这个后来补题也是wa，计数并查集合并公式推错（这么简单卧槽我小学数学没学好），然后最愚蠢的是排序的时候把m写成了n，wa到哭。
其实当时第一眼看就大概想到是用计数的并查集做，但是没想到自己能写这么挫，而且当时主要是被那个二叉树卡住（怀疑人生+2），那个真的只要简单粗暴就好我却想多了，唉
算是学到了缩点构造新图的方法吧emm有点笨
有环的图一般都有点难倒腾，所以这种都是遇见了先求scc，变成DAG以后再想办法求解。
分析题意后可以发现，对于DAG，求出来的其实是一条路径，因为如果有分叉的话分叉的不同子树之间就没有办法互通了。令每个缩点的权值为含点的个数，这样就转化成了DAG上的最长路问题了。
错误：scc每次都会出现漏初始化错误。。。还有就是缩点之后的节点标记与原来的节点意义不同，要注意。
这题略坑。。。输入的可以是不连续的点，我一开始都从1开始dfs，WA了n发发现数据里可能没1这个点。。。GG
求割点的话本身倒是很裸，但是还要求出生成的子集个数，也是试了各种奇怪的方法。。。。后来发现把low[v]>=pre[u]的子节点v的数量记下来就可以了，至于证明。。。直觉证明法吧
继续阅读“[割点][强连通分量] POJ1523 SPF”
很久很久没做过图论的题了，做一个忽然意识到自己记错了欧拉回路的意义emmm
就当是复习一下吧。
昨天哈，喝了不少酒干了傻事，该过去的就让他翻篇吧，
继续阅读“[训练指南][简单题][图论] 无向图的欧拉回路 Uva10054”
