Skip to content

Commit 25f2604

Browse files
zimphazimpha
committed
add more codes
1 parent 024dc46 commit 25f2604

File tree

8 files changed

+395
-28
lines changed

8 files changed

+395
-28
lines changed

‎README.md

Lines changed: 30 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -25,56 +25,57 @@ Collections of some commonly used algorithms.
2525

2626
## Graph Algorithms
2727

28-
+ [x] 拓扑排序
29-
+ [ ] 最短路
30-
+ [ ] Floyd
31-
+ [ ] Bellman-Ford
32-
+ [ ] Dijkstra
33-
+ [ ] SPFA
34-
+ [ ] 最小生成树
28+
+ [x] [拓扑排序](graph-utility/TopoSort.cc)
29+
+ [x] 最短路
30+
+ [x] [Floyd/无向图最小环](graph-utility/Floyd.cc)
31+
+ [x] [Dijkstra](graph-utility/shortest-path.cc)
32+
+ [x] [SPFA](graph-utility/shortest-path.cc)
33+
+ [ ] 生成树
3534
+ [ ] Prim
3635
+ [ ] Kruskal
3736
+ [ ] Borůvka
3837
+ [ ] 度限制最小生成树
39-
+ [ ] 最小树形图
40-
+ [ ] 最大流
41-
+ [ ] 费用流
42-
+ [x] dominator tree
43-
+ [ ] 二分图匹配
44-
+ [ ] 匈牙利算法
45-
+ [ ] Hopcroft
46-
+ [x] Kuhn-Munkres算法
38+
+ [x] [最小树形图](graph-utility/Edmonds.cc)
39+
+ [ ] 次小生成树
40+
+ [ ] Matrix Tree Theorem
41+
+ [x] [最大流](graph-utility/NetworkFlow.cc)
42+
+ [x] [费用流](graph-utility/CostFlow.cc)
43+
+ [x] [Dominator Tree](graph-utility/DominatorTree.cc)
44+
+ [x] 二分图匹配
45+
+ [x] [匈牙利算法](graph-utility/Hungarian.cc)
46+
+ [x] [Hopcroft](graph-utility/Hopcroft.cc)
47+
+ [x] [Kuhn-Munkres算法](graph-utility/KuhnMunkres.cc)
4748
+ [ ] 一般图匹配
48-
+ [ ] 最大匹配
49+
+ [x] [最大匹配](graph-utility/Blossom.cc)
4950
+ [ ] 最大权匹配
50-
+ [x] 2-SAT
51-
+ [x] 有向图强联通分量
52-
+ [x] 无向图割点/割边
53-
+ [x] 弦图判定
54-
+ [x] 图的绝对中心(Kariv Hakimi算法)
51+
+ [x] [2-SAT](graph-utility/TwoSat.cc)
52+
+ [x] [有向图强联通分量](graph-utility/SCC.cc)
53+
+ [x] [无向图割点/割边](graph-utility/ArticulationPoints.cc)
54+
+ [x] [弦图判定](graph-utility/ChordalGraph.cc)
55+
+ [x] [图的绝对中心](graph-utility/KarivHakimi.cc)
5556
+ [ ] Pseudoforest
5657
+ [ ] Cactus Graph
5758
+ [ ] 欧拉回路
5859
+ [ ] 虚树
5960
+ [ ] 最近公共祖先
6061
+ [ ] Prüfer序列
6162
+ [ ] 最大团
62-
+ [x] 全局最小割
63+
+ [x] [全局最小割](graph-utility/StoerWagner.cc)
6364
+ [ ] Gomory-Hu tree
6465
+ [ ] 树hash
6566
+ [ ] 树上最长路
66-
+ [ ] Matrix Tree Theorem
6767
+ [ ] Tutte matrix
6868

6969
## Data Structures
7070

7171
+ [ ] easy segment tree
72-
+ [x] 树状数组
73-
+ [x] ST表
74-
+ [x] 并查集
75-
+ [ ] 莫队算法
76-
+ [x] 动态凸壳
72+
+ [x] [树状数组](data-structure/FenwickTree.cc)
73+
+ [x] [ST表](data-structure/SparseTable.cc)
74+
+ [x] [并查集](data-structure/Disjoint-Set.cc)
75+
+ [ ] [莫队算法](data-structure/Sqrt-Decomposition.cc)
76+
+ [x] [动态凸壳](data-structure/DynamicConvexHull.cc)
7777
+ [ ] 树链剖分
78+
+ [x] [树分治](data-structure/Centroid-Decomposition.cc)
7879
+ [ ] 二叉堆
7980
+ [ ] 左偏树
8081
+ [ ] Splay
@@ -128,6 +129,7 @@ Collections of some commonly used algorithms.
128129
+ [x] 单纯型
129130
+ [x] 组合数取模
130131
+ [x] 多项式插值
132+
+ [ ] 连分数
131133

132134
## Other Useful Tools
133135

‎data-structure/Centroid-Decomposition.cc

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#include <vector>
2+
#include <algorithm>
3+
4+
namespace centroid {
5+
std::vector<int> sz, mark;
6+
int total, mins, rt;
7+
void init(int n) {
8+
sz.resize(n);
9+
mark.assign(n, 0);
10+
}
11+
void get_center(int u, int f, std::vector<int> G[]) {
12+
int mx = 0; sz[u] = 1;
13+
for (auto &&v: G[u]) if (v != f && !mark[v]) {
14+
get_center(v, u, G);
15+
sz[u] += sz[v];
16+
mx = std::max(mx, sz[v]);
17+
}
18+
mx = std::max(mx, total - sz[u]);
19+
if (mx < mins) mins = mx, rt = u;
20+
}
21+
void run(int u, int tot, std::vector<int> G[]) {
22+
total = tot, mins = tot * 2, rt = u;
23+
get_center(u, -1, G);// find centroid
24+
mark[u = rt] = true;
25+
get_center(u, -1, G);// recalculate subtree size
26+
for (auto &v: G[u]) if (!mark[v]) {
27+
run(v, sz[v], G);
28+
}
29+
}
30+
}

‎data-structure/Sqrt-Decomposition.cc

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
#include <cmath>
2+
#include <cstdio>
3+
#include <vector>
4+
#include <algorithm>
5+
6+
namespace Normal {
7+
const int MAXN = 100000 + 10, P = 333;
8+
struct Q {
9+
int l, r, id;
10+
bool operator < (const Q &rhs) const {
11+
return l / P == rhs.l / P ? r < rhs.r : l < rhs.l;
12+
}
13+
} seq[MAXN];
14+
int A[MAXN], ans[MAXN], n, m;
15+
namespace Block {
16+
int u[MAXN], now;
17+
void init() {}
18+
void add(int x) {}
19+
void del(int x) {}
20+
}
21+
void run() {
22+
scanf("%d%d", &n, &m);
23+
for (int i = 0; i < n; ++i) scanf("%d", A + i);
24+
for (int i = 0; i < m; ++i) {
25+
scanf("%d%d", &seq[i].l, &seq[i].r);
26+
seq[i].id = i;
27+
}
28+
std::sort(seq, seq + m);
29+
Block::init();
30+
for (int i = 0, l = 0, r = -1; i < m; ++i) {
31+
int L = seq[i].l, R = seq[i].r;
32+
while (r < R) Block::add(A[++r]);
33+
while (r > R) Block::del(A[r--]);
34+
while (l < L) Block::del(A[l++]);
35+
while (l > L) Block::add(A[--l]);
36+
ans[seq[i].id] = Block::now;
37+
}
38+
}
39+
}
40+
41+
namespace Tree {
42+
typedef long long LL;
43+
const int MAXN = 100000 + 10, K = 17, M = 1e9 + 7;
44+
std::vector<int> G[MAXN];
45+
int dep[MAXN], f[MAXN][K + 1];
46+
int st[MAXN], ed[MAXN], loc[MAXN << 1];
47+
int n, m, P, dfn;
48+
void dfs(int x, int par = -1) {
49+
loc[st[x] = dfn++] = x;
50+
for (int i = 1; i <= K; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
51+
for (auto &y: G[x]) if (y != par) {
52+
dep[y] = dep[f[y][0] = x] + 1;
53+
dfs(y, x);
54+
}
55+
loc[ed[x] = dfn++] = x;
56+
}
57+
int lca(int x, int y) {
58+
if (x == y) return x;
59+
if (dep[x] < dep[y]) std::swap(x, y);
60+
for (int i = K; ~i; --i) {
61+
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
62+
}
63+
if (x == y) return x;
64+
for (int i = K; ~i; --i) {
65+
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
66+
}
67+
return f[x][0];
68+
}
69+
int val[MAXN], cnt[MAXN], vis[MAXN], sum;
70+
void deal(int x) {//这部分维护序列
71+
int c = val[x]; vis[x] ^= 1;
72+
sum -= !!cnt[c];
73+
if (!vis[x]) cnt[c]--;
74+
else cnt[c]++;
75+
sum += !!cnt[c];
76+
}
77+
struct Node {
78+
int l, r, z, id;
79+
bool operator < (const Node &rhs) {
80+
return l / P == rhs.l / P ? r < rhs.r : l / P < rhs.l / P;
81+
}
82+
} Q[MAXN];
83+
int ans[MAXN];
84+
void run() {
85+
scanf("%d", &n);
86+
for (int i = 1; i <= n; ++i) scanf("%d", val + i);
87+
for (int i = 1; i < n; ++i) {
88+
int u, v; scanf("%d%d", &u, &v);
89+
G[u].push_back(v);
90+
G[v].push_back(u);
91+
}
92+
dfs(dep[1] = 1);
93+
P = sqrt(n * 2);
94+
scanf("%d", &m);
95+
for (int i = 0; i < m; ++i) {
96+
int x, y; scanf("%d%d", &x, &y);
97+
if (st[x] > st[y]) std::swap(x, y);
98+
int z = lca(x, y); Q[i].id = i;
99+
if (z == x) Q[i].l = st[x], Q[i].r = st[y];
100+
else Q[i].l = ed[x], Q[i].r = st[y], Q[i].z = z;
101+
}
102+
std::sort(Q, Q + m);
103+
for (int i = 0, l = 0, r = -1; i < m; ++i) {
104+
if (r < Q[i].r) {
105+
for (++r; r <= Q[i].r; ++r) deal(loc[r]);
106+
--r;
107+
}
108+
for (; r > Q[i].r; --r) deal(loc[r]);
109+
for (; l < Q[i].l; ++l) deal(loc[l]);
110+
if (l > Q[i].l) {
111+
for (--l; l >= Q[i].l; --l) deal(loc[l]);
112+
++l;
113+
}
114+
if (Q[i].z) deal(Q[i].z);
115+
ans[Q[i].id] = sum;
116+
if (Q[i].z) deal(Q[i].z);
117+
}
118+
for (int i = 0; i < m; ++ i) printf("%d\n", ans[i]);
119+
}
120+
}
121+
122+
namespace Modified {
123+
}

‎graph-utility/Blossom.cc

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
#include <queue>
2+
#include <vector>
3+
#include <algorithm>
4+
5+
class Blossom { // 复杂度O(n^3)
6+
public:
7+
const static int MAXN=1000+10; // 最大结点个数
8+
int mate[MAXN],n,ret; // mate[]为配偶结点的编号，没有匹配上的点为-1
9+
//传入结点个数n及各结点的出边G[], 返回匹配点对的数量ret
10+
int run(int n, const std::vector<int> G[]) {
11+
this->n = n;
12+
std::fill(mate, mate + n, -1);
13+
for (int i=0;i<n;++i) if (mate[i]==-1) aug(i, G);
14+
for (int i=ret=0;i<n;++i) ret+=(mate[i]>i);
15+
return ret;
16+
}
17+
private:
18+
int next[MAXN],dsu[MAXN],mark[MAXN],vis[MAXN];
19+
std::queue<int> Q;
20+
int get(int x) {return (x==dsu[x])?x:(dsu[x]=get(dsu[x]));}
21+
void merge(int a,int b) {dsu[get(a)]=get(b);}
22+
int lca(int x,int y) {
23+
static int t=0; ++t;
24+
for (; ; std::swap(x, y)) if (x != -1) {
25+
if (vis[x=get(x)]==t) return x; vis[x]=t;
26+
x=(mate[x]!=-1)?next[mate[x]]:-1;
27+
}
28+
}
29+
void group(int a,int p) {
30+
for (int b,c;a!=p;merge(a,b),merge(b,c),a=c) {
31+
b=mate[a],c=next[b];
32+
if (get(c)!=p) next[c]=b;
33+
if (mark[b]==2) mark[b]=1, Q.push(b);
34+
if (mark[c]==2) mark[c]=1, Q.push(c);
35+
}
36+
}
37+
void aug(int s,const std::vector<int> G[]) {
38+
for (int i=0;i<n;++i) next[i]=vis[i]=-1,dsu[i]=i,mark[i]=0;
39+
while (!Q.empty()) Q.pop(); Q.push(s); mark[s]=1;
40+
while (mate[s]==-1&&!Q.empty()) {
41+
int x=Q.front(); Q.pop();
42+
for (int i=0,y;i<(int)G[x].size();++i) {
43+
if ((y=G[x][i])!=mate[x]&&get(x)!=get(y)&&mark[y]!=2) {
44+
if (mark[y]==1) {
45+
int p=lca(x,y);
46+
if (get(x)!=p) next[x]=y;
47+
if (get(y)!=p) next[y]=x;
48+
group(x,p); group(y,p);
49+
}
50+
else if (mate[y]==-1) {
51+
next[y]=x;
52+
for (int j=y,k,l;j!=-1;j=l) {
53+
k=next[j]; l=mate[k];
54+
mate[j]=k; mate[k]=j;
55+
}
56+
break;
57+
}
58+
else {
59+
next[y]=x; Q.push(mate[y]);
60+
mark[mate[y]]=1; mark[y]=2;
61+
}
62+
}
63+
}
64+
}
65+
}
66+
};

‎graph-utility/Arborescence.cc renamed to ‎graph-utility/Edmonds.cc

File renamed without changes.

‎graph-utility/Floyd.cc

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
template<typename T>
2+
struct Floyd {
3+
static const int SIZE = 1000 + 10;
4+
std::vector<int> path;
5+
T dis[SIZE][SIZE], res;
6+
int src[SIZE][SIZE];
7+
// 传入结点个数n及权值矩阵graph[][]，返回最小环的长度res，方案记在path中
8+
// 对于矩阵graph[][]中不存在的边，权值设为1e9+7或0x7F7F7F7F之类的极大值
9+
// 若最后的返回值大于等于1e9，则不存在最小环
10+
T run(int n, const T graph[SIZE][SIZE]) {
11+
res = 1e9 + 7;
12+
for (int i = 0; i < n; ++i) {
13+
for (int j = 0; j < n; ++j) {
14+
src[i][j] = -1;
15+
dis[i][j] = graph[i][j];
16+
}
17+
}
18+
for (int k = 0; k < n; ++k) {
19+
for (int i = 0; i < k; ++i) {
20+
for (int j = i + 1; j < k; ++j) {
21+
T tmp = graph[k][i] + graph[j][k];
22+
if (dis[i][j] > res - tmp) continue;
23+
path.clear();
24+
get_path(i, j);
25+
path.push_back(k);
26+
path.push_back(i);
27+
res = tmp + dis[i][j];
28+
}
29+
}
30+
for (int i = 0; i < n; ++i) {
31+
for (int j = 0; j < n; ++j) {
32+
T tmp = dis[i][k] + dis[k][j];
33+
if (tmp < dis[i][j]) {
34+
dis[i][j] = tmp;
35+
src[i][j] = k;
36+
}
37+
}
38+
}
39+
}
40+
return res;
41+
}
42+
void get_path(int i, int j) {
43+
int k = src[i][j];
44+
if (k != -1) {
45+
get_path(i, k);
46+
get_path(k, j);
47+
} else {
48+
path.push_back(j);
49+
}
50+
}
51+
};

0 commit comments

Comments
 (0)