Spy97

图论

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 计算几何(30) 贪心(2)

/ 注册

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

2019杭电多校第三场 HDU6604 支配树

题意给出一个DAG，入度为0的点为控制点，现在有两个点要沿边走向控制点，问破坏哪些点可以使其中一个无法到达，求点的个数题解支配树模板题，可惜之前没听说过 😦 逆向建图，然后让0号点连接所有控制中心，对于 a ...

2019-07-30

0 458

2019牛客多校第三场 Graph Games

题意给出一个无向图， S ( x ) ...

2019牛客多校 Graph Games

2019-07-26

0 413

NOIP 2015 运输计划树上差分二分答案

#include<bits/stdc++.h> #define N 300010 #define INF 0x3f3f3f3f #define eps 1e-10 #define pi 3.141592653589793 #define P 1000000007 #define LL ...

2019-06-06

0 457

ZOJ 4097 Rescue the Princess

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5986 题意 n n ...

2019-04-17

0 419

华中科技大学程序设计邀请赛网络赛 F War

题意给出一个n个点的树，询问编号在一个区间内的点到给定点的最近距离。题解分块暴力求解，整块中用SPFA预处理，零散的用LCA求解。首先根据内存限制，计算出打开能开 200 ...

2019-04-14

0 650

Kruskal重构树

建树方法在Kruskal求最小/最大生成树的基础上，假设要加入的u、v两点，边权为w，设u、v两点的father为fu、fv，新建一个点（从n+1开始标号）p，father[fu]=father[fv]=p，将点p的点权设为w。使用方法：最小生成树的任意两点的最大值：将边从小到...

Kruskal重构树

2018-09-13

0 444

HDU 6393

题意：一个n个点，n条边的图，2中操作，1是将某条边的权值更改，2是询问两点的最短距离。题解：由于n个点，n条边，所以是树加一个环，将环上的边随意取出一条，就是1颗树，以取出的边的一个端点为根，建立有根树。虚线就是取出的边。红色为环上的边。对于更改边的权值的操作，用dfs序+区...

2018-08-15

0 497

HDU 6326

题意：一棵结点数为n的树，除1号结点外都有一个怪兽，消灭第i个结点上的怪兽会消耗ai的HP，但消灭完之后会恢复bi的HP。现在从结点1出发去打怪，最少初始时含有多少HP才能保证能打完所有的怪，而且任何时候的HP都不为负。题解：以1为根，将无根树变为有根树。要想消灭结点x的怪兽，必须先消灭x的...

2018-07-31

0 487

HDU 6331

题意：给一张有向图，q个询问，询问s到t至少经过k条路的最近距离。题解： f[k][i][j]表示从i到j经过k条路的最短路，则f[k][i][j]=min{f[k-1][i][t]+map[t][j]},(1<=t<=n),这个方程很好理解，从i到j经过k条路，我们枚举中间点t...

2018-07-31

0 375

二分图总结

定义：一组点集可以分为两部分，且每部分内各点互不相连，两部分的点之间可以有边。判定：所有回路的长度都是偶数，即不存在长度为奇数的环。二分图最大匹配算法：匈牙利算法，时间复杂度，最坏 O（点数 × 边数） //二分图匹配 //n为男生数目，m为女生数目 //line[i][j]第i...

2018-04-13

0 432