希胤

图论模板

dp模板(4) dp狂练(1) 小知识(3) 数论模板(1) 未归档(3) 杂模板(5) 题解(36)

/ 注册

全部文章 / 图论模板（共4篇）

网络流

相关概念网络流（似水流）（整张图流出的水流）网络流的本质是水流问题源点：水流出的点(只有一个) 汇点：水流进的点(只有一个) 弧(边)：水流容量(用小c表示) 可行流：一条路径(s ==> t)和(此路径能流过的最大水流)【可行流 = 路径边 + 能流过的最大水流】可改进路(增广路)：...

2021-08-29

0 395

图的连通性

有向图：割点：删掉不连通割边（桥）：删掉不连通连通分量：极大子图点双连通图：删任意一点仍连通，即没有割点边双连通图：删任意一边仍连通，即没有桥点双连通分量：极大点双连通子图边双连通分量：极大边双连通子图（单点也是边双连通分量）边双连通：删桥后，双方都是边双有向图：弱连通：单...

2021-08-20

0 321

二分图

二分图：图中有两个点集，集合内的点互不连边，两个集合的点互相连边二分图最大匹配：在二分图找到最多的匹配数匈牙利算法：时间复杂度：邻接矩阵:O(n^3) 邻接表:O(n*m) int e[N][N]; //邻接矩阵 //可以用邻接表稍微优化一下 int vis[N],link[N]; ...

2021-04-25

0 308

lca之树上倍增（模板）

题目参考博客参考代码 #include<bits/stdc++.h> using namespace std; int const M=5e5+7; int const N=5e5+7; int n,m,s; struct node{ int a,next,len; }e[M<...

2021-04-01

0 311