Skip to content

Commit cefb6c8

Browse files
zimphazimpha
committed
add LCA and modify some codes
1 parent a3b98a0 commit cefb6c8

13 files changed

+119
-57
lines changed

‎graph-utility/ArticulationPoints.cc

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,10 @@
22
class Articulation {
33
public:
44
typedef std::pair<int, int> PII;
5-
static const int SIZE = 100005; // 最大结点个数
5+
static const int N = 100005; // 最大结点个数
66
std::vector<PII> keyE; // keyE为割边集，keyV为割点集
7-
std::vector<int> keyV, cc[SIZE]; // cc[p]表示结点p在哪些双连通分量中
8-
int cnt; // 对于旧版编译器，将上面cc[SIZE]改成vector的形式
7+
std::vector<int> keyV, cc[N]; // cc[p]表示结点p在哪些双连通分量中
8+
int cnt; // 对于旧版编译器，将上面cc[N]改成vector的形式
99
// 传入结点个数n及各结点的出边e[]，返回双连通分量的个数cnt
1010
int run(int n, const std::vector<int> G[]){
1111
memset(dfn, use = 0, sizeof(dfn[0]) * n);
@@ -18,7 +18,7 @@ class Articulation {
1818
return cnt;
1919
}
2020
private:
21-
int dfn[SIZE], low[SIZE], dot[SIZE], use;
21+
int dfn[N], low[N], dot[N], use;
2222
void dfs(int x, int dep, const std::vector<int> G[]){
2323
int src = 0, out = 1 < dep;
2424
dot[use++] = x;

‎graph-utility/Blossom.cc

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,8 @@
44

55
class Blossom { // 复杂度O(n^3)
66
public:
7-
const static int MAXN=1000+10; // 最大结点个数
8-
int mate[MAXN],n,ret; // mate[]为配偶结点的编号，没有匹配上的点为-1
7+
const static int N = 1000 + 10; // 最大结点个数
8+
int mate[N], n, ret; // mate[]为配偶结点的编号，没有匹配上的点为-1
99
//传入结点个数n及各结点的出边G[], 返回匹配点对的数量ret
1010
int run(int n, const std::vector<int> G[]) {
1111
this->n = n;
@@ -15,7 +15,7 @@ class Blossom { // 复杂度O(n^3)
1515
return ret;
1616
}
1717
private:
18-
int next[MAXN],dsu[MAXN],mark[MAXN],vis[MAXN];
18+
int next[N],dsu[N],mark[N],vis[N];
1919
std::queue<int> Q;
2020
int get(int x) {return (x==dsu[x])?x:(dsu[x]=get(dsu[x]));}
2121
void merge(int a,int b) {dsu[get(a)]=get(b);}

‎graph-utility/DominatorTree.cc

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,11 +25,13 @@
2525
* 相反dom中节点u在原图G中的标号是pt[u]
2626
* 调用build得到以s为根的Dominator Tree
2727
**/
28+
#include <vector>
29+
2830
namespace DominatorTree {
29-
const static int MAXN = 100000 + 10;
31+
const static int N = 100000 + 10;
3032
typedef std::vector<int> VI;
31-
int dfn[MAXN], pre[MAXN], pt[MAXN], sz;
32-
int semi[MAXN], dsu[MAXN], idom[MAXN], best[MAXN];
33+
int dfn[N], pre[N], pt[N], sz;
34+
int semi[N], dsu[N], idom[N], best[N];
3335
int get(int x) {
3436
if (x == dsu[x]) return x;
3537
int y = get(dsu[x]);

‎graph-utility/Edmonds.cc

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,16 @@
33
//传入图的大小n和邻接阵G[][], 不相邻点边权inf, 下标0~n-1
44
//可更改边权的类型, pre[]返回树的构造, 用父结点表示
55
//传入时pre[]数组清零, 用-1标出可能的源点
6-
const int MAXN = 1000 + 10, inf = 1e9;
7-
int edmonds(int n, int G[][MAXN], int pre[]) {
8-
static int vis[MAXN][MAXN], l[MAXN], p[MAXN];
6+
#include <cstring>
7+
8+
const int N = 1000 + 10, inf = 1e9;
9+
int edmonds(int n, int G[][N], int pre[]) {
10+
static int vis[N][N], l[N], p[N];
911
int m=n,cnt,ret=0;
1012
for (int i=0;i<n;++i) l[i]=i;
1113
do {
12-
memset(vis,0,sizeof(vis)); memset(p,0xff,sizeof(p));
14+
memset(vis,0,sizeof(vis));
15+
memset(p,0xff,sizeof(p));
1316
cnt=m; for (int i=0;i<m;++i) vis[i][i]=1;
1417
for (int i=0;i<cnt;++i) if (l[i]==i&&pre[i]!=-1) {
1518
for (int j=0;j<m;++j) {

‎graph-utility/Floyd.cc

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
1+
#include <vector>
2+
13
template<typename T>
24
struct Floyd {
3-
static const int SIZE = 1000 + 10;
5+
static const int N = 1000 + 10;
46
std::vector<int> path;
5-
T dis[SIZE][SIZE], res;
6-
int src[SIZE][SIZE];
7+
T dis[N][N], res;
8+
int src[N][N];
79
// 传入结点个数n及权值矩阵graph[][]，返回最小环的长度res，方案记在path中
810
// 对于矩阵graph[][]中不存在的边，权值设为1e9+7或0x7F7F7F7F之类的极大值
911
// 若最后的返回值大于等于1e9，则不存在最小环
10-
T run(int n, const T graph[SIZE][SIZE]) {
12+
T run(int n, const T graph[N][N]) {
1113
res = 1e9 + 7;
1214
for (int i = 0; i < n; ++i) {
1315
for (int j = 0; j < n; ++j) {

‎graph-utility/Hopcroft.cc

Lines changed: 12 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,15 @@
1+
#include <vector>
2+
#include <algorithm>
3+
14
class Hopcroft {
25
public:
3-
static const int SIZE = 100005; // 最大的单侧点个数
4-
int cnt,pos[SIZE],neg[SIZE]; // pos[]为左侧点所匹配到的右侧点编号
6+
static const int N = 100005; // 最大的单侧点个数
7+
int cnt,pos[N],neg[N]; // pos[]为左侧点所匹配到的右侧点编号
58
// neg[]反之，没有匹配到对应的点则为-1
69
// 传入左侧点个数n和左侧点至右侧点的边表e[]，返回匹配点对的数量cnt
7-
int gao(int n, const vector<int> e[]){ // 复杂度O(sqrt(n)*m)
8-
fill(pos,pos+n,-1); fill(neg,neg+n,-1);
10+
int gao(int n, const std::vector<int> e[]){ // 复杂度O(sqrt(n)*m)
11+
std::fill(pos,pos+n,-1);
12+
std::fill(neg,neg+n,-1);
913
for(int x=cnt=0,y;x<n;x++){
1014
for(size_t i=0;i<e[x].size();i++){
1115
if(~neg[y=e[x][i]]) continue;
@@ -15,7 +19,8 @@ class Hopcroft {
1519
}
1620
while(true){
1721
int push=0,pop=0,ok=0;
18-
fill(lx,lx+n,-1); fill(ly,ly+n,-1);
22+
std::fill(lx,lx+n,-1);
23+
std::fill(ly,ly+n,-1);
1924
for(int x=0;x<n;x++) if(pos[x]<0) lx[q[push++]=x]=0;
2025
while(push!=pop){
2126
int x=q[pop++],y;
@@ -32,8 +37,8 @@ class Hopcroft {
3237
}
3338
}
3439
private:
35-
int lx[SIZE],ly[SIZE],q[SIZE];
36-
bool aug(int x, const vector<int> e[]){
40+
int lx[N],ly[N],q[N];
41+
bool aug(int x, const std::vector<int> e[]){
3742
int c=lx[x]+1,y=lx[x]=-1;
3843
for(size_t i=0;i<e[x].size();i++) if(ly[y=e[x][i]]==c){
3944
ly[y]=-1;

‎graph-utility/KarivHakimi.cc

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,9 +5,11 @@
55
* 返回一个pair, 表示绝对中心在这条边(s1, s2)上
66
* ds1, ds2记录s1和s2距离绝对中心的距离, 按需返回
77
**/
8-
const int MAXN = 1000, inf = 1e9;
8+
#include <algorithm>
99

10-
void floyd(int n, int g[][MAXN], int d[][MAXN]) {
10+
const int N = 1000, inf = 1e9;
11+
12+
void floyd(int n, int g[][N], int d[][N]) {
1113
for (int i = 0; i < n; ++i) {
1214
for (int j = 0; j < n; ++j) {
1315
d[i][j] = g[i][j];
@@ -22,8 +24,8 @@ void floyd(int n, int g[][MAXN], int d[][MAXN]) {
2224
}
2325
}
2426

25-
std::pair<int, int> KarivHakimi(int n, int g[][MAXN]) {
26-
static int rk[MAXN][MAXN], d[MAXN][MAXN];
27+
std::pair<int, int> KarivHakimi(int n, int g[][N]) {
28+
static int rk[N][N], d[N][N];
2729
double ds1 = 0, ds2 = 0;
2830
floyd(n, g, d);
2931
for (int i = 0; i < n; ++i) {

‎graph-utility/KuhnMunkres.cc

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
1-
#include <bits/stdc++.h>
1+
#include <algorithm>
22

33
struct KM {
44
typedef long long cost_t;
5-
static const int MAXN = 1000;
5+
static const int N = 1000;
66
static const cost_t inf = 1e9;
7-
cost_t lx[MAXN], ly[MAXN], sl[MAXN];
8-
int px[MAXN],py[MAXN],sy[MAXN],fa[MAXN],n;
7+
cost_t lx[N], ly[N], sl[N];
8+
int px[N],py[N],sy[N],fa[N],n;
99
void aug(int v) {
1010
sy[v]=py[v]; if (px[sy[v]]!=-2) aug(px[sy[v]]);
1111
}
12-
bool find(int v, const cost_t w[][MAXN]) {
12+
bool find(int v, const cost_t w[][N]) {
1313
for (int i=0;i<n;++i) if (!~py[i]) {
1414
if (sl[i]>lx[v]+ly[i]-w[v][i]) {
1515
sl[i]=lx[v]+ly[i]-w[v][i]; fa[i] = v;
@@ -22,7 +22,7 @@ struct KM {
2222
}
2323
return 0;
2424
}
25-
cost_t gao(int _n, const cost_t w[][MAXN], cost_t m=inf) {
25+
cost_t gao(int _n, const cost_t w[][N], cost_t m=inf) {
2626
n=_n; std::fill(sy,sy+n,-1); std::fill(ly,ly+n,0);
2727
for (int i=0;i<n;++i) lx[i]=*std::max_element(w[i],w[i]+n);
2828
for (int i(0),flag;i<n;++i) {

‎graph-utility/LCA.cc

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
#include <cstdio>
2+
#include <vector>
3+
#include <cstring>
4+
#include <algorithm>
5+
6+
namespace LCA {
7+
const int N = 100000 + 10, POW = 15;
8+
int fa[N][POW + 1], dep[N];
9+
void dfs(std::vector<int> G[], int u, int p = -1) {
10+
memset(fa[u], -1, sizeof(fa[u]));
11+
fa[u][0] = p;
12+
dep[u] = p == -1 ? 0 : dep[p] + 1;
13+
for (auto &&v: G[u]) dfs(G, v, u);
14+
}
15+
void build(int n) {
16+
for (int i = 1; (1 << i) <= n; ++i) {
17+
for (int j = 0; j < n; ++j) if (~fa[j][i - 1]) {
18+
fa[j][i] = fa[fa[j][i - 1]][i - 1];
19+
}
20+
}
21+
}
22+
int up(int u, int d) {
23+
for (int i = 0; d; ++i, d >>= 1) {
24+
if (d & 1) u = fa[u][i];
25+
}
26+
return u;
27+
}
28+
int ask(int u, int v) {
29+
if (dep[u] < dep[v]) std::swap(u, v);
30+
u = up(u, dep[u] - dep[v]);
31+
for (int i = POW; i >= 0; --i) {
32+
if (fa[u][i] == fa[v][i]) continue;
33+
u = fa[u][i];
34+
v = fa[v][i];
35+
}
36+
if (u != v) u = fa[u][0];
37+
return u;
38+
}
39+
}

‎graph-utility/NetworkFlow.cc

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,25 @@
1+
#include <cstring>
2+
#include <algorithm>
3+
14
namespace NetFlow {
2-
const int MAXN=100000,MAXM=100000,inf=1e9;
5+
const int N=100000,MAXM=100000,inf=1e9;
36
struct Edge {
47
int v,c,f,nx;//c:capcity, f:flow
58
Edge() {}
69
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
710
} E[MAXM];
8-
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
11+
int G[N],cur[N],pre[N],dis[N],gap[N],n,sz;
912
void init(int _n) {
10-
N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
13+
n=_n,sz=0; memset(G,-1,sizeof(G[0])*n);
1114
}
1215
void link(int u,int v,int c) {
1316
E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
1417
E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
1518
}
1619
int ISAP(int S,int T) {//S -> T
1720
int maxflow=0,aug=inf,flag=false,u,v;
18-
for (int i=0;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=0;
19-
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false) {
21+
for (int i=0;i<n;++i)cur[i]=G[i],gap[i]=dis[i]=0;
22+
for (gap[S]=n,u=pre[S]=S;dis[S]<n;flag=false) {
2023
for (int &it=cur[u];~it;it=E[it].nx) {
2124
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+1) {
2225
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
@@ -32,7 +35,7 @@ namespace NetFlow {
3235
}
3336
}
3437
if (flag) continue;
35-
int mx=N;
38+
int mx=n;
3639
for (int it=G[u];~it;it=E[it].nx) {
3740
if (E[it].c>E[it].f&&dis[E[it].v]<mx) {
3841
mx=dis[E[it].v]; cur[u]=it;
@@ -44,7 +47,7 @@ namespace NetFlow {
4447
return maxflow;
4548
}
4649
bool bfs(int S,int T) {
47-
static int Q[MAXN]; memset(dis,-1,sizeof(dis[0])*N);
50+
static int Q[N]; memset(dis,-1,sizeof(dis[0])*n);
4851
dis[S]=0; Q[0]=S;
4952
for (int h=0,t=1,u,v,it;h<t;++h) {
5053
for (u=Q[h],it=G[u];~it;it=E[it].nx) {
@@ -60,7 +63,7 @@ namespace NetFlow {
6063
int ret=0,tmp,v;
6164
for (int &it=cur[u];~it&&ret<low;it=E[it].nx) {
6265
if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f) {
63-
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f))) {
66+
if (tmp=dfs(v,T,std::min(low-ret,E[it].c-E[it].f))) {
6467
ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp;
6568
}
6669
}
@@ -70,7 +73,7 @@ namespace NetFlow {
7073
int dinic(int S,int T) {
7174
int maxflow=0,tmp;
7275
while (bfs(S,T)) {
73-
memcpy(cur,G,sizeof(G[0])*N);
76+
memcpy(cur,G,sizeof(G[0])*n);
7477
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
7578
}
7679
return maxflow;

‎graph-utility/SCC.cc

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,11 @@
1+
#include <cstring>
2+
#include <vector>
3+
14
struct Tarjan {// index from 0 to n - 1
2-
static const int MAXN = 100000 + 10;
3-
std::vector<int> SCC[MAXN];
4-
int low[MAXN], dfn[MAXN], col[MAXN];
5-
int stk[MAXN], top, scc_cnt, sz;
5+
static const int N = 100000 + 10;
6+
std::vector<int> SCC[N];
7+
int low[N], dfn[N], col[N];
8+
int stk[N], top, scc_cnt, sz;
69
void dfs(int x, const std::vector<int> G[]) {
710
low[x] = dfn[x] = ++sz;
811
stk[++top] = x;
@@ -25,8 +28,8 @@ struct Tarjan {// index from 0 to n - 1
2528
}
2629
void run(int n,const std::vector<int> G[]) {
2730
sz = top = scc_cnt = 0;
28-
memset(dfn, 0, sizeof(dfn));
29-
memset(col, -1, sizeof(col));
31+
memset(dfn, 0, sizeof(*dfn) * n);
32+
memset(col, -1, sizeof(*col) * n);
3033
for (int i = 0; i < n; ++i) {
3134
if (!dfn[i]) dfs(i,G);
3235
}

‎graph-utility/StoerWagner.cc

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,9 @@
22
#include <cstring>
33

44
// global minimum-cut
5-
const int MAXN = 500 + 10, inf = 1e9;
6-
int stoer_wagner(int n, int G[][MAXN]) {
7-
int dis[MAXN], idx[MAXN], vis[MAXN], ret = inf;
5+
const int N = 500 + 10, inf = 1e9;
6+
int stoer_wagner(int n, int G[][N]) {
7+
int dis[N], idx[N], vis[N], ret = inf;
88
for (int i = 0; i < n; ++ i) idx[i] = i;
99
while (n > 1) {
1010
int t = 1, s = 0;

‎graph-utility/TwoSat.cc

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,13 @@
22
// 调用add_edge()添加边, 调用add_var()添加变量的初始值
33
// 调用solve()求解2sat 如果有解存在mark中
44
// 对于变量x, x*2表示x, x*2+1表示~x, mark[x*2]表示x的值
5+
#include <vector>
6+
#include <algorithm>
7+
58
struct TwoSAT {
6-
static const int MAXN = 200000 + 10;
7-
std::vector<int> G[MAXN];
8-
int mark[MAXN], S[MAXN], sz, n;
9+
static const int N = 200000 + 10;
10+
std::vector<int> G[N];
11+
int mark[N], S[N], sz, n;
912
void init(int n) {
1013
this->n = n;
1114
for (int i = 0; i < n * 2; ++i) G[i].clear();
@@ -20,7 +23,7 @@ struct TwoSAT {
2023
return true;
2124
}
2225
bool solve() {
23-
fill(mark, mark + 2 * n, 0);
26+
std::fill(mark, mark + 2 * n, 0);
2427
for (int i = 0; i < n * 2; i += 2) {
2528
if (mark[i] || mark[i ^ 1]) continue;
2629
sz = 0;

0 commit comments

Comments
 (0)