生之、如舟

图论

动态规划(8) 博弈论(1) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

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

G. Reducing Delivery Cost 【最短路+暴力】2100

G. Reducing Delivery Cost 题意一个1000点，1000条边的通联图，你可以令一条边权值为0，然后使得之后的1000条s到e的最短路总和最小。解法对每个点求一个到其他所有点的最短路，然后枚举每条边a，b。s到e的最短路就是ps: 自己对每条路进行标记，然后跑最短路的...

图论2500

2020-11-18

0 670

C. Link Cut Centroids 【树的重心】1700

C. Link Cut Centroids 思路把一个重心下的子树上的一个叶子节点，移动到另一个重点作为孩子节点即可代码 #include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),co...

图论2000以下

2020-11-16

0 679

E. The Road to Berland is Paved 【2-sat】1900

E. The Road to Berland is Paved With Good Intentions 题意有N个点，M条边的无向图，有些边是0，有些边是1，现在给定一个操作：选择一个点，把其相连接点边的0/1状态取反，问最多N次操作，可不可能把所有边都变成1？如果可以，输出方案解法 ...

图论2000以下 2-sat

2020-11-12

0 563

0-1 MST 【MST】1900

0-1 MST Examplesinput 6 11 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6output 2input 3 0output 0题意给你一个N个点的完全图，再指定哪些边是权值为1的边，没有指定的就是权值为0的边。问其最小生成树的权值...

最小生成树图论2000以下

2020-11-12

0 727

D. Solve The Maze 【图论】1700分

D. Solve The Maze Vivek has encountered a problem. He has a maze that can be represented as an 𝑛×𝑚 grid. Each of the grid cells may represent the fo...

图论基础题

2020-11-10

0 717

图论基础题

Pairs 判断边是否完全覆盖 1500分Toad Ivan has 𝑚 pairs of integers, each integer is between 1 and 𝑛, inclusive. The pairs are (𝑎1,𝑏1),(𝑎2,𝑏2),…,(𝑎𝑚,𝑏𝑚)....

图论基础题

2020-11-09

0 625

Atcoder ABC155F Perils in Parallel 【构造图】【差分】【离散化】

Perils in Parallel 题目意思就是有N个分布在不同点的炸弹，其状态有激活和未激活两种，我们可以有M个区间可供选择，对选择区间内的炸弹状态反转。问，是否可以将所有的炸弹置为未激活状态。若可以，请输出从小到大输出选择了那些区间。分析首先进行离散化，以题目样例1举例： 3 4 5 ...

构造差分

2020-03-02

0 1293