C++ STL:SET & MULTISET

C++ STL:SET & MULTISET

定义

方式 效果
set <数据类型名> 集合名; 先定义一个容器,容器内无任何元素
set <数据类型名> 集合名(另一个集合名); 定义一个集合并用另一个集合初始化(只能是数据类型相同的集合,不能是数组)
set <数据类型名> 集合名(另一个集合名.begin(), 另一个集合名.end()); 定义一个集合并用另一个集合初始化(只能是数据类型相同的集合,不能是数组)
set <数据类型名> 集合名[集合数量]; 定义集合数组
set <Elem> 产生一个set,以 (operator <) 为排序准则
set <Elem, cmp> 产生一个set,以cmp为排序准则
阅读更多
数论:整除问题

数论:整除问题

整除分块

与其说整除分块是一种算法,不如说它是一个技巧。有时我们需要计算这样的式子:

$$
\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor
$$

根据经验,我们发现 $\lfloor\frac{n}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。对于每种取值,$i$ 都会有一个连续的范围。假设函数 $f$ 的前缀和可以预处理后快速求出,那么我们可以枚举 $\lfloor\frac{n}{i}\rfloor$ 的所有取值,并和 $f$ 的连续一段的和相乘。具体可以见代码:

1
2
3
4
5
6
7
// s[i] 为函数 f(i) 的前缀和 
int ans = 0;
for(int i=1, j; i<=n; i=j+1) {
j = n/(n/i);
ans += (s[j]-s[i-1])*(n/i);
}
printf("%d\n", ans);
阅读更多
图论

图论

图论算法一般都是揉在一起的,很难单独把算法拆开讲,所以直接上题目吧。分类是大致分的,其实有很多是交叉的。

二叉树

二叉树的遍历有三种,分别为前序遍历,中序遍历和后序遍历,并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

阅读更多
Hexo:配置 SSH 公钥部署

Hexo:配置 SSH 公钥部署

配置 git 使用 ssh 密钥

git 支持 https 和 git 两种传输协议。其实两种方式都可以,但是如果使用https协议,每次pull、push都要输入密码(大部分电脑上),所以建议使用ssh密钥对认证,可实现免密且更加安全。下面将介绍Hexo如何配置 SSH 公钥部署。

示例在Windows环境下。

阅读更多
涉江

涉江

  E 座的尽头是一扇窗。她喜欢伏在那里的窗棂上,很多个课间。窗外是一幢天井;三面环楼,夐不见曦。

  天井的中央是一台鱼池。一到每年新生入学的时候,鱼们便如笋般冒了出来,流水潺潺,清荣峻茂;整个学校也像鱼池一样变得活络了起来。人们的脸上总是挂着笑容;鱼池旁也缀上了很多人影,来来往往的。

阅读更多
还在用 STL 排序?

还在用 STL 排序?

使用 C 库函数

很多人都不知道的是,其实 C 语言也是自带排序函数的,就是位于 <stdlib.h> 库中的 qsort

函数声明:

阅读更多
网络流:最小割

网络流:最小割

将图 $G$ 分为 $A$ 和 $B$ 两个点集,$A$ 和 $B$ 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。

S - T 最小割

特别地,对于一个网络,在满足 $源点 s \in 点集{S}, 汇点 t \in 点集{T}(S\cap T= \varnothing)$ 的情况下,从 S 到 T 的边的权值和被称为 S 到 T 的割

阅读更多
网络流:最大流

网络流:最大流

EK

增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径,调整流值和残留网络 ,直到没有增广路为止

EK 算法就是不断的找最短路,找的方法就是每次找一条边数最少的增广(即最短路径增广)。

最多要增广多少次?

可以证明,最多 O(VE)​ 次增广,可以达到最大流。

如何找到一条增广路?

先明确什么是增广路。增广路是一条从s到t的路径,路径上每条边残留容量都为正。把残留容量为正的边设为可行的边,那么我们就可以用简单的 BFS 得到边数最少的增广路。

阅读更多
CF387D

CF387D

题意分析

操作最少的次数,构成有趣图,注意无重边,有向边。

  • 操作分为加边和删边。
  • 有趣图定义
    • 有一个中心,满足此点有自环,且与其他结点有双向边。
    • 除中心点外的结点,满足出度 = 入度 = 2。
阅读更多
匹配:模板

匹配:模板

UOJ78 二分图最大匹配(DFS - KM)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 550;

int match[N], g[N][N], vis[N], link[N];
int n, m, e, tag, ans = 0;

bool dfs(int u) {

for(int v=1; v<=m; ++v) {
if(!g[u][v] or vis[v] == tag) continue;
vis[v] = tag;
if(!match[v] or dfs(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int main() {

scanf("%d%d%d", &n, &m, &e);
for(int i=1, u, v; i<=e; ++i) {
scanf("%d%d", &u, &v);
g[u][v] = true;
}

for(int i=1; i<=n; ++i) {
tag = i;
if(dfs(i)) ++ans;
}

printf("%d\n", ans);
for(int i=1; i<=m; ++i) link[match[i]] = i;

for(int i=1; i<=n; ++i) printf("%d ", link[i]);

return 0;
}

UOJ79 一般图最大匹配(带花树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 550;
int fa[N], match[N], pre[N], vis[N];
int tag = 0, n, m, ans = 0;
int flag[N];
bool g[N][N];
queue<int> q;

void clear(queue<int> &q) {
queue<int> empty;
swap(q, empty);
}
int belong(int u) {
return fa[u] == u ? u : fa[u] = belong(fa[u]);
}

void path(int u) {
while(u) {
int v = match[pre[u]];
match[u] = pre[u];
match[pre[u]] = u;
u = v;
}
}
int lca(int u, int v) {
++tag;
u = belong(u);
v = belong(v);
while(vis[u] != tag) {
vis[u] = tag;
u = belong(pre[match[u]]);
if(v) swap(u, v);
}
return u;
}
void connect(int u, int v, int root) {
while(belong(u) != root) {
pre[u] = v;
v = match[u];
if(flag[v] == 2) {
q.push(v);
flag[v] = 1;
}
if(belong(u) == u) fa[u] = root;
if(belong(v) == v) fa[v] = root;
u = pre[v];
}
}
bool bfs(int u) {

memset(flag, 0, sizeof flag);
memset(pre, 0, sizeof pre);
for(int i=1; i<=n; ++i) fa[i] = i;

clear(q);
q.push(u);
flag[u] = 1;

while(!q.empty()) {
u = q.front();
q.pop();
for(int v=1; v<=n; ++v) {
if(!g[u][v]) continue;
if(flag[v] == 0) {
pre[v] = u;
if(match[v] == 0) {
path(v);
return true;
}
q.push(match[v]);
flag[v] = 2;
flag[match[v]] = 1;
} else {
if(flag[v] == 2) continue;
if(belong(u) == belong(v)) continue;
int root = lca(u, v);
connect(u, v, root);
connect(v, u, root);
}
}
}
return false;
}
int main() {

scanf("%d%d", &n, &m);
for(int i=1, u, v; i<=m; ++i) {
scanf("%d%d", &u, &v);
g[u][v] = g[v][u] = true;
}

for(int i=1; i<=n; ++i)
if(match[i] == 0 and bfs(i)) ++ans;

printf("%d\n", ans);
for(int i=1; i<=n; ++i) printf("%d ", match[i]);

return 0;
}

UOJ80 二分图最大权匹配(BFS - KM)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 440;
const LL INF = 0x3f3f3f3f3f3f3f3f;

bool vis[N];
int pre[N], link[N], res[N];
int n, m, e;
LL g[N][N], lx[N], ly[N], d[N], ans = 0;

void bfs(int k) {

int x, y = 0;
LL min1 = INF, delta;
memset(vis, false, sizeof vis);
memset(pre, 0, sizeof pre);
memset(d, 0x3f, sizeof d);
link[y] = k;

do {
x = link[y], delta = INF, vis[y] = true;
for(int i=1; i<=m; ++i) {
if(!vis[i]) {
if(d[i] > lx[x] + ly[i] - g[x][i]) {
d[i] = lx[x] + ly[i] - g[x][i];
pre[i] = y;
}
if(delta > d[i]) delta = d[i], min1 = i;
}
}
for(int i=0; i<=m; ++i)
if(vis[i]) lx[link[i]] -= delta, ly[i] += delta;
else d[i] -= delta;
y = min1;
} while(link[y]);
while(y) link[y] = link[pre[y]], y = pre[y];
}

int main() {

scanf("%d%d%d", &n, &m, &e);
m = max(n, m);
for(int i=1; i<=e; ++i) {
int u, v; LL w;
scanf("%d%d%lld", &u, &v, &w);
g[u][v] = w;
lx[u] = max(lx[u], w);
}

for(int i=1; i<=n; ++i) bfs(i);

for(int i=1; i<=m; ++i) {
if(!g[link[i]][i]) continue;
ans += g[link[i]][i];
res[link[i]] = i;
}
printf("%lld\n", ans);
for(int i=1; i<=n; ++i) printf("%d ", res[i]);

return 0;
}