图论 题解 oi http://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/170/summaryhttp://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/170/summary A POJ2914 Lutece 2710 Minimum Cut C 容易证明只有行号列号之和奇偶性相同...

图论 题解 oi https://www.luogu.com.cn/problem/P4208https://www.luogu.com.cn/problem/P4208 题意 求 个节点, 条边的无向图的不同的最小生成树个数. 问题本身的性质 多尝试几个样例可以发现, 同一个图的所有最小生成树中, 相同边权的边的数量是一定相等的. 通过 Kruscal 算法的贪心过程容易证明这个结论:...

图论 题解 oi https://www.luogu.com.cn/problem/P4716https://www.luogu.com.cn/problem/P4716 题意 最小树形图是有向图上，从给定的根节点出发到达所有节点的一颗生成树。 分析 求解最小树形图的一种算法是的朱刘算法。 考虑给除根节点外的每个点寻找一条最小的入边，如果找出的入边恰好构成一棵树，则容易证明这样的情况1是最优...

图论 题解 oi http://poj.org/problem?id=2914http://poj.org/problem?id=2914 题意 个点 条边（最多完全图）的带权无向图，问至少删去的边权之和，使删边后图不连通。（任意两点的最小割）。 分析 显然枚举两点用最大流最小割来求跑不过。介绍此类问题的模板做法：Stoer-Wagner 算法，主要思想是枚举寻找任意两点的最小割，每处理...

图论 oi 一道题 今天考试考了这么一道题: 出题人给出一颗以1为根的树, 一开始每个节点都是一颗棋子, 一面白一面黑, 白色的面朝上接下来就q次操作, 操作分两种: 0操作: 将一颗棋子翻转 1操作:询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号 空间 256M 时间 1.5s, 数据范围 8e5, 考场上果断写树剖, 可惜我人傻常数大, T到75分(有人用树剖过了)....

图论 题解 oi http://codeforces.com/problemset/problem/575/Ghttp://codeforces.com/problemset/problem/575/G 9月30日的 Codeforces Div.2 的题解大概就鸽了吧 题意 个点条边的带权图, 求到的最小权值且最小长度的路径, 权值为把路径经过的边的权从终点到起点往依次写下组成的十进制...

图论 题解 oi https://www.luogu.org/problem/P2149https://www.luogu.org/problem/P2149 @liao_rl今天下午神秘兮兮的宣称洛谷上有道题4个标4种做法都被hack了, 于是我就看见了这个题. 好像也没有什么难的吧, 几乎一遍就A了原题和hack数据(交的前两遍数组没开够) 做法比较显然吧, 4次最短路得到的最短路径...