弓长九日

图论

CDQ(1) codeforces(1) DP(9) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 线段树(8) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

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

leetcode第178场周赛_1368.使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况： 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1] 2 ，下一步往左走，也就是你会从 gr...

2020-03-03

0 628

Codeforces Round #597 (Div. 2) D. Shichikuji and Power Grid [图论虚点]

Shichikuji and Power Grid https://codeforces.com/contest/1245/problem/D 题意：给了你一堆城市让你给他们建发电站 or 把他们连到有点的城市我们道路的花费会是题目中给的 ...

2019-11-02

0 908

Codeforces Round #586 (Div. 1 + Div. 2) D. Alex and Julia (数论|二部图性质)

D. Alex and Julian https://codeforces.com/contest/1220/problem/D 二分图性质无奇环而且我们取尝试一些数据发现最后省的奇数最多才是最好的 1 3 5 7 9 2 6 10 14 18 其中 1 2 是不可能同时出现所以这...

2019-09-22

0 565

[最短路] HDU 5521 Meeting （最短路 + 虚点）

题目大意：有N个点，给定M个集合，集合Si里面的点两两之间的距离都为Ti，集合里面的所有点数之和<=1e6。两个人分别从1和n出发，要求相遇的最短距离，并输出相遇的点（可能多个）。解题思路：首先无疑是最短路，然后因为同一个点可能属于两个或多个集合，故需要虚电。除了n个点外，每一个集合建一个新...

2019-08-21

0 524

牛客小白月赛16 小雨坐地铁（分层最短路|优化建图）2019暑期多校训练营（第六场）D move

一种优化分层图建图方法直接暴力建这样线特别乱得图因为中转得关系我们得暴力扫完这些中转用一个虚拟点代表中专这样建就直接处理得换线得问题了考虑分层图最短路。很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(nm^2)的，可能会超时...

2019-08-16

0 546

2019HDU杭电多校第三场 HDU 6611 K Subsequence (最小费用最大流 + dijkstra 模版(处理负边))

唉自己 spfaT了之后又写了份 dj的还是T了只能说自己写的好丑啊一直写spfa 突然不适以下标程扒的以后当模板使用了 #include<bits/stdc++.h> using namespace std; typedef pair<int, int>...

2019-08-08

0 787

[网络流24题] 最长不下降子序列问题

LOJ 特判 n == 1 注意最后对 1， n 点得处理就好 HDU 多校第3场前置知识 I HDU 6611 K Subsequence 所有我先补了这题 #include <bits/stdc++.h> using namespace std; typedef unsigne...

2019-08-07

0 607

2019HDU多校第二场 HDU 6598 Harmonious Army (最小割)

还是第一次见到网络流还能这么见图的找最小割看最大匹配价值的 mark 学习了割图肯定分成要不和s连要不和t连如果多个点之间还有价值同时在一个集合中比如把 a， b 割了总价值 - 最小割我们会把e算进去不丢掉点与点之间的价值割边的时候这些情况都照顾到了我们解方程建边 ...

2019-07-31

0 434

[网络流图匹配 + 二分] 导弹防御塔 CH6803

我们考虑跑网络流首先是二分图最大匹配 == 入侵者数量时时间可以缩小点才最多50个 50 * 50 最多发 3000 不到的导弹 3000 和原点连 3000个边 3000 和入侵者连最多15000边开前向星按 40000 * 8 边差不多了就因为连的太多了暴力点建图将...

2019-07-30

0 460

[差分约束] P3275 [SCOI2011] 糖果 & P1993 小K的农场 (洛谷) & poj 3169 Layout

差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。最长路找最小值 <= 数据最低的极限最短路找最大值 >= 数据最大的极限这个是极限是存在得不能<=...

2019-03-27

0 832