whix

图论

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

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

LCA及应用

定义：最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。性质： 1. L C ...

2020-01-30

0 445

Rank of Tetris HDU - 1811【拓扑排序+并查集】

#include <bits/stdc++.h> //基本思路：先用并查集处理 = 关系，归为一个集合，每次对该集合内的元素进行操作时，只对父亲操作即可。 //然后利用拓扑排序处理级别关系 using namespace std; const int N=1e4+5; int pre[N...

2020-01-22

0 439

牛客小白月赛21-D.DDoS【拓扑图路径计数，边权无用】

题面： Nancy的男朋友喜欢网络安全！最近，一种新的DDoS——脉冲波悄然来临。其基本原理是利用不同线路服务器的延时，使得Request同时到达目标服务器，以堵塞其它正常的通讯。不妨假设攻击者在1号节点，目标服务器在nn号节点，其余节点（2到n-1号节点）为中继服务器。攻击者可以在任意时间发...

2020-01-19

0 441

CodeForce 1272 E. Nearest Opposite Parity【多源bfs+反向建图】

#include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=2e5+5; vector<int>path[N]; int a[N],ans[N],d[N]; int n...

2020-01-10

0 378

Shichikuji and Power Grid CodeForces - 1245D【最小生成树-点权变边权-超级源点】

没有做过这种题目，所以当时就没有做出来，其实即使建立一个超级源点，和每个点相连，以建发电站的费用为边权，其他的点之间的边权就按题目给的算。然后跑一遍最小生成树即可，我用的是prim。注意数据范围(>_<),因为这个一直WA。 #include <bits/stdc++.h>...

2019-12-30

0 516

拓扑排序及应用

【1】Reward HDU - 2647 拓扑排序，反向建边 AC代码： #include <bits/stdc++.h> using namespace std; const int N=1e4+5; int reward[N]; vector<int>pic[N]; i...

2019-12-29

0 532

开关问题

poj3279 别人的代码，方便学习。 #include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #inc...

2019-11-15

0 487

确定比赛名次 HDU - 1285

一开始题目意思理解错了，以为要求求出所有选手的排名关系，看了题解后，才知道只要满足题目给的次序即可，没有给的信息，可以不用管。因此，问题就变成了拓扑排序的模板题。所谓的拓扑排序是相对于有向无圈图的顶点的一种排序，如果出现了从u到v的路径，那么排序后，v一定在u的后面。基本操作就是，每次先找到入度...

2019-08-19

0 517

二分图匹配

一.最大匹配：匈牙利算法：总体来说，就是不断找增广路，如果找到 i 可以匹配而没有匹配的点 j ，就将这个点 j 与 i 配对，而如果发现要匹配的点 j 已经和 k 配对了，就对这个点 j 所配对的点 k 进行寻找增广路的操作，看这个点k 能不能另外找到其他的点 x 来替代 j 点来进行配对,如...

2019-08-14

0 490

网络流

最大流：算法： 1.Ford_Fulkerson(F_F算法) 2.EK算法 3.dinic算法 EK: 基于暴力搜索思想的方法，每次都采用bfs去寻找从源点到汇点的增广路，直到找不到，即表示找到了最大流，每次找到一条增广路（找的时候记得存下路径）后，可以求出这条路上的最小流量，即为这条增广路的流...

2019-08-09

0 571