AtCoder Petrozavodsk Contest 001 D – Forest 连通块+并查集+贪心
D - Forest My Solution 题意：给出一个由n个点m条边构成的森林，每个点有个权值val[i]，额外加一条边(u,v)的花费是val[u] + val[v]，且u、v只能被用到一次，添加一些边使得图连通，求最小花费。 连通块+并查集+贪…
HDU – 6203 ping ping ping LCA倍增算法+dfs序+线段树
ping ping ping LCA倍增算法+dfs序+线段树 Source HDU - 6203 My Solution 题意：给出一颗以0为根有n+1个节点的树，给出p个条件，每个条件表示u,v之间有一个坏的节点，根据这p个条件求出树上至少有多少坏…
Codeforces Round #408 (Div. 2) D. Police Stations 最短路、BFS
D. Police Stations 最短路、BFS My Solution 题意：有一棵无根树，有一些节点上有一些标记(police station)，初始时满足，每个节点至少 与一个被标记过的节点相连且距离不超过d，要求去掉尽可能多的节点，使…
UESTC 1641 此情无计可消除，才下眉头，却上心头。 最小生成树、Kruskal
此情无计可消除，才下眉头，却上心头。 最小生成树、Kruskal Source 2017 UESTC Training for Graph Theory UESTC 1641 此情无计可消除，才下眉头，却上心头。 My Solution 题意：有一个长度为n的未知的01…
UESTC 1143 传输数据 网络流 最大流 Dinic
传输数据 网络流 最大流 Dinic Source 2015 UESTC Training for Graph Theory The question is from here. My Solution 最大流的Dinic算法 O(N^2 *M) N vertices and M edges #include #inclu…
计蒜之道 2017 程序设计大赛 – 计蒜客 复赛 D 百度地图导航 最短路、Dijkstra的拓展
计蒜之道 2017 程序设计大赛 - 计蒜客 复赛 D 百度地图导航 最短路、Dijkstra的拓展 Source 计蒜之道 2017 程序设计大赛 - 计蒜客 复赛 D 百度地图导航 计蒜客 15969 百度地图导航 My Solution 题意：有 n …
UESTC 1646 穷且益坚，不坠青云之志。 差分约束、Fellman-ford
穷且益坚， 不坠青云之志。差分约束、Fellman-ford Source 2017 UESTC Training for Graph Theory UESTC 1646 穷且益坚， 不坠青云之志。 My Solution 题意：求一个有n个元素的数列，满足任意连续p个数的…
HihoCoder – 1174 拓扑排序·一 拓扑排序、BFS
拓扑排序·一 拓扑排序、BFS Source HihoCoder - 1174 My Solution 拓扑排序基础题，判断图中是否有环。 拓扑排序、BFS 每次把入度为0的点删除后入队，进行BFS，最后如果有剩余没有删除的点，则存在环，否则…
UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造
去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造 Source 2017 UESTC Training for Graph Theory UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞 My Solution 题意：给出一个大小为n的集合S，集…
SGU – 465 Fire Station Building floyd+三分
Fire Station Building floyd+三分 Source SGU - 465 Gym - 100206B My Solution 题意：有n个城市m条双向边，计划在一条道路上建立一个消防局，并且它离城市的距离不能小于R，每个城市i有一个发生火灾的概率pi，要…
Gym – 101147H H. Commandos DAG
H - 记忆里在微甜 DAG Source Gym - 101147H My Solution 题意：即普通的DAG加了一维。 DAG上的dp 三维的有向无环图上dp， dp[k][i][j] = max(dp[k][i][j], dp[k][i+1][j] + mp[k][i][j]); dp[k][i][j] = max(dp[k…
Codeforces Round #385 (Div. 2) C. Hongcow Builds A Nation 并查集+贪心+组合学、图论、dfs
C. Hongcow Builds A Nation 并查集+贪心+组合学、图论、dfs My Solution 题意：有n个点(其中有k个关键点)，m条边，要求添加尽可能多的边使得k个关键点之间没有路径，问最多可以添加多少条边。 并查集+贪…
Codeforces Round #376 (Div. 2) C. Socks 并查集+贪心、图论
C. Socks 并查集+贪心、图论 Source Codeforces Round #376 (Div. 2) My Solution 并查集+贪心、图论 在读入的时候直接把有边相连的点维护到一个集合里，最后对于处理出的森林，可以用map<int, map<…
Codeforces Round #372 (Div. 2) D. Complete The Graph 图论、最短路、Dijkstra、路径、分配部分边权
D. Complete The Graph 图论、最短路、Dijkstra、路径、分配部分边权 Source Codeforces Round #372 (Div. 2) My Solution 图论、最短路、Dijkstra、路径、分配部分边权 首先去点2种不可能的情况： 1、不…
Codeforces Round #369 (Div. 2) D. Directed Roads 图论、组合学、二重dfs、并查集形式的图、Interesting、好题
D. Directed Roads 图论、组合学、二重dfs、并查集形式的图、Interesting、好题 Source Codeforces Round #369 (Div. 2) My Solution 图论、组合学、 二重dfs、并查集形式的图、Interesting、好题 可以把…
Codeforces Round #362 (Div. 2) C. Lorenzo Von Matterhorn LCA(最近公共祖先)
C. Lorenzo Von Matterhorn LCA(最近公共祖先) Source Codeforces Round #362 (Div. 2) My Solution LCA(最近公共祖先) 在有根树中，找出某两个结点u和v最近的公共祖先（或者说，离树根最远的公共祖先）…
UESTC 1146 秋实大哥与连锁快餐店 最小生成树、Prim
秋实大哥与连锁快餐店 最小生成树、Prim Source 2015 UESTC Training for Graph Theory The question is from here. My Solution 最小生成树 Prim算法 O(n^2); 旗舰店与旗舰店距离为0； TLE(3000ms) 了好多…
UESTC 1144 Big Brother 二分图、最大匹配
Big Brother 二分图、最大匹配 Source 2015 UESTC Training for Graph Theory The question is from here. My Solution 最大匹配问题 匈牙利算法， (似乎也可以用它的改进版，Hopcroft-Karp算法) #includ…
