ACM算法专用模板(持续更新中)

标签:位运算,gcd,exgcd,欧拉筛,快速乘,快速幂,矩阵快速幂,中国剩余定理,欧拉函数,逆元,高斯消元,生成函数,斯特林数,卡特兰数,SG函数与Nim博弈,奇异函数与威佐夫博弈,并查集,ST,线段树,主席树,树状数组,树链剖分,莫队,LCA,Trie树,KMP,AC自动机,后缀自动机,匈牙利算法,KM算法,Floyed,dijkstra,dijkstra+heap优化,SPFA及LLL与SLF优化,Dinic,MCMF,Kruscal,Prim

数据结构

基础

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fa[maxn];
void init(){
for(int i = 0; i < maxn; i++){
fa[i] = i;
}
}
int root(int x){
return x==fa[x] ? x : x=root(fa[x]);
}
void Union(int px, int py){
px = root(px);
py = root(py);
if(px != py){
fa[py] = px;
}
}

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int head[maxn], cnt;
struct EDGE{
int next, to, u, w;
}edge[maxm];
void add(int u, int v, int w){
edge[cnt].next = head[u];
edge[cnt].u = u;
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt++;
}
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
//memset(edge, 0, sizeof(edge));
}

树结构

LCA(Tarjan)

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e4 + 7;
const int inf = 0x3f3f3f3f;
int n, head[maxn], fa[maxn], head_2[maxn], cnt, cnt_2, sx;
bool vis[maxn];
struct EDGE{
int next, to, u;
}edge[maxn];
struct QUERY{
int next, to, u, lca;
}query[maxn];
void add_edge(int u, int v){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].u = u;
head[u] = cnt++;
}
void add_query(int u, int v){
query[cnt_2].next = head_2[u];
query[cnt_2].to = v;
query[cnt_2].u = u;
head_2[u] = cnt_2++;
query[cnt_2].next = head_2[v];
query[cnt_2].to = u;
query[cnt_2].u = v;
head_2[v] = cnt_2++;
}
void init_edge(){
memset(head, -1, sizeof(head));
cnt = 0;
}
void init_query(){
memset(head_2, -1, sizeof(head_2));
cnt_2 = 0;
}
int root(int x){
return x = x == fa[x] ? x : root(fa[x]);
}
void tarjan(int x) {
fa[x] = x;
for (int i = head[x]; i != -1; i = edge[i].next) {
int v = edge[i].to;
tarjan(v);
fa[root(v)] = x;
}
vis[x] = true;
for (int i = head_2[x]; i != -1; i = query[i].next) {
int v = query[i].to;
if (vis[v]) {
query[i].lca = query[i^1].lca = root(v);
}
}
}
void read(){
int u, v;
scanf("%d", &n);
memset(vis, false, sizeof(vis));
for(int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
add_edge(u, v);
vis[v] = true;
}
for(int i = 1; i<=n; i++){
if(!vis[i]){
sx = i;
break;
}
}
memset(vis, false, sizeof(vis));
scanf("%d%d", &u, &v);
add_query(u, v);
}
void solve(){
tarjan(sx);
for(int i = 0; i < cnt_2; i+=2){
printf("%d\n", query[i].lca);
}
}
int main(){
int T;
scanf("%d", &T);
while(T--){
init_edge();
init_query();
read();
solve();
}
return 0;
}
/*
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
*/
//4 3

RMQ

普通莫队

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
/*	解释:
belong[x]x属于分块后的哪一块,Q[i]每个询问
modify(p,t)对p位置进行t修改,一般只有增加或者缩减这两种操作,具体问题具体分析
注意:
最后也可以不对询问id排序,直接保存到一个数组里面输出即可
*/
int a[nmax], belong[nmax];
ll ans = 0;
struct node {int l, r, id;ll ans;} Q[nmax];
bool cmp(node a, node b) {
if (belong[a.l] != belong[b.l]) return a.l < b.l;
else return a.r < b.r;
}
bool cmpid(node a, node b) {return a.id < b.id;}
void modify(int pos, int tag) {
// ......... 增删操作
}
int main() {
scanf("%d %d", &n, &m);
int sz = sqrt(n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;
belong[i] = (i - 1) / sz + 1;
}
sort(Q + 1, Q + 1 + m, cmp);
int l = 1, r = 0;
for (int i = 1; i <= m; ++i) {
while (l < Q[i].l) modify(l++, -1);
while (l > Q[i].l) modify(--l, 1);
while (r > Q[i].r) modify(r--, -1);
while (r < Q[i].r) modify(++r, 1);
Q[i].ans = ans;
}
sort(Q + 1, Q + 1 + m, cmpid);
for (int i = 1; i <= m; ++i) printf("%I64d\n", Q[i].ans);
return 0;
}

图论

最短路

Dijkstra(邻接矩阵)

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 3007;
const int inf = 0x3f3f3f3f;
int road[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int n, m, sx, ex;
void init(){
memset(road, inf, sizeof(road));
}
int dijkstra(int sx, int ex){
memset(vis, false, sizeof(vis));
memset(dis, inf, sizeof(dis));
dis[sx] = 0;
for(int u = 1; u<=n; u++){
int minD = inf, k = -1;
for(int i = 1; i<= n; i++){
if(!vis[i] && dis[i] < minD){
k = i;
minD = dis[i];
}
}
//if(k == ex)
// return dis[ex];
vis[k] = true;
for(int i = 1; i<= n; i++){
if(!vis[i] && dis[k] + road[k][i] < dis[i]){
dis[i] = dis[k] + road[k][i];
}
}
}
return dis[ex];
}
void read(){
int u, v, w;
sx = 1, ex = n;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
road[u][v] = min(road[u][v], w);
//road[v][u] = min(road[v][u], w); //双向边
}
}
void solve(){
printf("%d\n", dijkstra(sx, ex));
}
int main(){
while(~scanf("%d%d", &n, &m)){
init();
read();
solve();
}
return 0;
}

Dijkstra

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 3007;
const int inf = 0x3f3f3f3f;
struct EDGE{
int next, to, w;
}edge[maxn<<4];
int head[maxn], dis[maxn], cnt;
bool vis[maxn];
int n, m, sx, ex;
void add(int u, int v, int w){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt++;
}
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
}
int dijkstra(int sx, int ex){
memset(vis, false, sizeof(vis));
memset(dis, inf, sizeof(dis));
dis[sx] = 0;
for(int cas = 1; cas<=n; cas++){
int minD = inf, kk = -1;
for(int i = 1; i<= n; i++){
if(!vis[i] && dis[i] < minD){
kk = i;
minD = dis[i];
}
}
//if(kk == ex)
// return dis[ex];
vis[kk] = true;
for(int i = head[kk]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(!vis[v] && dis[kk] + edge[i].w < dis[v]){
dis[v] = dis[kk] + edge[i].w;
}
}
}
return dis[ex];
}
void read(){
int u, v, w;
sx = 1, ex = n;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
//add(v, u, w); //双向边
}
}
void solve(){
printf("%d\n", dijkstra(sx, ex));
}
int main(){
while(~scanf("%d%d", &n, &m)){
init();
read();
solve();
}
return 0;
}

Dijkstra+heap

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 3007;
const int inf = 0x3f3f3f3f;
struct EDGE{
int next, to, w;
}edge[maxn<<4];
int head[maxn], dis[maxn], cnt;
bool vis[maxn];
int n, m, sx, ex;
struct NODE{
int u;
int dis;
NODE(){}
NODE(int x, int y) : u(x), dis(y){}
bool operator <(const NODE &a)const{
return dis>a.dis;
}
};
void add(int u, int v, int w){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt++;
}
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
}
int dijkstra(int sx, int ex){
memset(vis, false, sizeof(vis));
memset(dis, inf, sizeof(dis));
dis[sx] = 0;
priority_queue<NODE>que;
que.push(NODE(sx, 0));
while(!que.empty()){
NODE tmp = que.top();
que.pop();
int kk = tmp.u;
if(vis[kk]){
continue;
}
vis[kk] = true;
for(int i = head[kk]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(!vis[v] && dis[kk] + edge[i].w < dis[v]){
dis[v] = dis[kk] + edge[i].w;
que.push(NODE(v, dis[v]));
}
}
}
return dis[ex];
}
void read(){
scanf("%d%d", &n, &m);
int u, v, w;
sx = 1, ex = n;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w); //双向边
}
}
void solve(){
printf("%d\n", dijkstra(sx, ex));
}
int main(){
int T;
while(T--){
init();
read();
solve();
}
return 0;
}

SPFA

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+7;
int n, m, sx, ex;
int head[maxn], dis[maxn], cnt;
bool vis[maxn];
struct EDGE{
int next, to, w, u;
}edge[maxn<<3];
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].u = u;
edge[cnt].w = w;
head[u] = cnt++;
}
int SPFA(int sx, int ex){
memset(vis, false, sizeof(vis));
memset(dis, inf, sizeof(dis));
queue<int>que;
dis[sx] = 0;
que.push(sx);
while(!que.empty()){
int kk = que.front();
que.pop();
vis[kk] = false;
for(int i = head[kk]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(dis[v] > dis[kk] + edge[i].w){
dis[v] = dis[kk] + edge[i].w;
if(!vis[v]){
vis[v] = true;
que.push(v);
}
}
}
}
return dis[ex];
}
int main(){
while(~scanf("%d%d", &n, &m)){
init();
sx = 1, ex = n;
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
//add(v, u, w); //双向边
}
printf("%d\n", SPFA(sx, ex));
}
}

网络流

DINIC

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;
int n, m, sx, ex, cnt;
int head[maxn], pre[maxn];
struct EDGE{
int u, next, to, c;
}edge[maxn<<3];
void add_edge(int u, int v, int c){
edge[cnt].u = u;
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].c = c<=inf ? c : inf;
head[u] = cnt++;
}
void add(int u, int v, int c){
add_edge(u, v, c);
add_edge(v, u, 0);//双向边容量为c
}
void init(){
//memset(edge, 0, sizeof(edge));
memset(head, -1, sizeof(head));
cnt = 0;
}
void read(){
sx = 1, ex = n;
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d",&u, &v, &w);
add(u, v, w);
}
}
bool BFS(int sx, int ex){
memset(pre, 0, sizeof(pre));
queue<int>que;
que.push(sx);
pre[sx] = 1;
while(!que.empty()){
int kk = que.front();
que.pop();
for(int i = head[kk]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(!pre[v]&&edge[i].c){
pre[v] = pre[kk] + 1;
que.push(v);
}
}
}
return pre[ex] != 0;
}
int DFS(int pos, int flow){
if(pos == ex || flow == 0)
return flow;
int f = flow;
for(int i = head[pos]; i != -1; i = edge[i].next){
int tmp, v = edge[i].to;
if(edge[i].c && pre[pos] + 1 == pre[v] && (tmp = DFS(v, min(edge[i].c, flow)))>0){
edge[i].c -= tmp;
edge[i^1].c += tmp;
flow -= tmp;
if(flow == 0){
break;
}
}
}
return f - flow;
}
int Dinic(int sx, int ex){
int flow = 0;
while(BFS(sx, ex)){
flow += DFS(sx, inf);
}
return flow;
}
int main(){
while(~scanf("%d%d",&m, &n)){
init();
read();
printf("%d\n", Dinic(sx, ex));
}
return 0;
}

DINIC优化

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;
int n, m, sx, ex, cnt;
int head[maxn], pre[maxn], cur[maxn];
struct EDGE{
int u, next, to, c;
}edge[maxn<<3];
void add_edge(int u, int v, int c){
edge[cnt].u = u;
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].c = c<=inf ? c : inf;
head[u] = cnt++;
}
void add(int u, int v, int c){
add_edge(u, v, c);
add_edge(v, u, 0);//双向边容量为c
}
void init(){
//memset(edge, 0, sizeof(edge));
memset(head, -1, sizeof(head));
cnt = 0;
}
void read(){
sx = 1, ex = n;
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d",&u, &v, &w);
add(u, v, w);
}
}
bool BFS(int sx, int ex){
memset(pre, 0, sizeof(pre));
queue<int>que;
que.push(sx);
pre[sx] = 1;
while(!que.empty()){
int kk = que.front();
que.pop();
for(int& i = cur[kk]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(!pre[v]&&edge[i].c){
pre[v] = pre[kk] + 1;
que.push(v);
}
}
}
return pre[ex] != 0;
}
int DFS(int pos, int flow){
if(pos == ex || flow == 0)
return flow;
int f = flow;
for(int i = head[pos]; i != -1; i = edge[i].next){
int tmp, v = edge[i].to;
if(edge[i].c && pre[pos] + 1 == pre[v] && (tmp = DFS(v, min(edge[i].c, flow)))>0){
edge[i].c -= tmp;
edge[i^1].c += tmp;
flow -= tmp;
if(flow == 0){
break;
}
}
}
return f - flow;
}
int Dinic(int sx, int ex){
int flow = 0;
while(BFS(sx, ex)){
memcpy(cur, head, sizeof(head));
flow += DFS(sx, inf);
}
return flow;
}
int main(){
while(~scanf("%d%d",&m, &n)){
init();
read();
printf("%d\n", Dinic(sx, ex));
}
return 0;
}

DINIC(邻接矩阵)

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 307;
struct NODE{
int c;
int f;
};
int sx,ex;
int pre[maxn];
NODE road[maxn][maxn];
int n, m, N;
bool BFS(){
memset(pre,0,sizeof(pre));
queue<int>q;
q.push(sx);
pre[sx] = 1;
while(!q.empty()){
int d = q.front();
q.pop();
for(int i = 1;i<=N;i++){
if(!pre[i]&&road[d][i].c-road[d][i].f){
pre[i] = pre[d] + 1;
q.push(i);
}
}
}
return pre[ex]!=0;
}
int dfs(int pos, int flow){
int f = flow;
if(pos==ex)
return flow;
for(int i = 1; i <= N; i++){
if(road[pos][i].c - road[pos][i].f && pre[pos] + 1 == pre[i]){
int a = road[pos][i].c - road[pos][i].f;
int t = dfs(i, min(a, flow));
road[pos][i].f += t;
road[i][pos].f -= t;
flow -= t;
}
}
return f - flow;
}
int dinic(){
int sum = 0;
while(BFS()){
sum+=dfs(sx,inf);
}
return sum;
}
void init(){
N = n;
sx = 0;
ex = N;
memset(road,0,sizeof(road));
}
void read(){
int u,v,w;
for(int i = 1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
road[u][v].c+=w;
}
}
int main(){
while(~scanf("%d%d",&m,&n)){
init();
read();
printf("%d\n",dinic());
}
return 0;
}

MCMF

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxm = 1e5+7;
const int maxn = 1e4+7;
const int inf = 0x3f3f3f3f;
int n, m, cnt, sx, ex;
int head[maxn], pre[maxn], dis[maxn];
bool vis[maxn];
struct EDGE{
int next;
int to;
int w;
int c;
}edge[maxm];
void init(){
sx = 0;
ex = 1;
cnt = 0;
memset(edge, 0, sizeof(edge));
memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int c, int w){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].c = c<=inf ? c : inf;
edge[cnt].w = w;
head[u] = cnt++;
}
void add(int u, int v, int c, int w){
add_edge(u, v, c, w);
add_edge(v, u, 0, -w);
}
bool SPFA(int sx, int ex){
memset(pre, -1, sizeof(pre));
memset(dis, inf, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[sx] = 0;
queue<int>que;
que.push(sx);
while(!que.empty()){
int kk = que.front();
que.pop();
vis[kk] = false;
for(int i = head[kk]; i != -1; i = edge[i].next){
EDGE tmp = edge[i];
if(tmp.c && dis[tmp.to]>dis[kk]+tmp.w){
dis[tmp.to] = dis[kk] + tmp.w;
pre[tmp.to] = i;
if(!vis[tmp.to]){
vis[tmp.to] = true;
que.push(tmp.to);
}
}
}
}
return pre[ex] != -1;
}
int MCMF(int sx, int ex){
int flow = 0, cost = 0;
while(SPFA(sx, ex)){
int min_flow = inf;
for(int i = pre[ex]; i != -1; i = pre[edge[i^1].to]){
min_flow = min(min_flow, edge[i].c);
}
for(int i = pre[ex]; i != -1; i = pre[edge[i^1].to]){
edge[i].c -= min_flow;
edge[i^1].c += min_flow;
cost += min_flow * edge[i].w;
}
flow += min_flow;
}
return cost;
}
void read(){
int u, v, c, w;
ex = n+1;
for(int i = 0;i<m;i++){
scanf("%d%d%d%d",&u,&v,&c,&w);
add(u,v,c, w);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(n+m==0){
break;
}
init();
read();
printf("%d\n",MCMF(sx, ex));
}
return 0;
}

匹配

匈牙利算法(邻接矩阵)

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 107;
int N, K;
int edge[maxn][maxn], head[maxn];
bool vis[maxn];
void init(){
memset(edge, 0, sizeof(edge));
memset(head, 0, sizeof(head));
}
bool find_edge(int x) {
for (int i = 1; i <= N; i++) {
if (edge[x][i] && !vis[i]) {
vis[i] = true;
if (!head[i] || find_edge(head[i])) {
head[i] = x;
return true;
}
}
}
return false;
}
int Magyar(int N){
int ans = 0;
for (int i = 1; i <= N; i++) {
memset(vis, false, sizeof(vis));
if (find_edge(i)) {
ans++;
}
}
return ans;
}
int main() {
while (cin >> N >> K) {
int x, y;
for (int i = 1; i <= K; i++){
cin >> x >> y;
edge[x][y] = 1;
}
cout << Magyar(N) << endl;
}
return 0;
}

匈牙利算法

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 107;
int T, N, m;
int head[maxn], link[maxn];
bool vis[maxn];
int cnt;
struct EDGE{
int next, u, to, w;
}edge[maxn];
void add(int u, int v, int w){
edge[cnt].next = head[u];
edge[cnt].u = u;
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt++;
}
void init(){
memset(edge, 0, sizeof(edge));
memset(link, 0, sizeof(link));
memset(head, -1, sizeof(head));
cnt = 0;
}
bool find_edge(int x){
for(int i = head[x]; i!= -1; i = edge[i].next){
int v = edge[i].to;
if(!vis[v]){
vis[v] = true;
if (!link[v] || find_edge(link[v])) {
link[v] = x;
return true;
}
}
}
return false;
}
int Magyar(int N){
int ans = 0;
for (int i = 1; i <= N; i++) {
memset(vis, false, sizeof(vis));
if (find_edge(i)) {
ans++;
}
}
return ans;
}
int solve(){
int ans = Magyar(N);
return ans;
}
void read(){
scanf("%d%d",&N, &m);
while(m--){
int x, y;
scanf("%d%d",&x, &y);
add(x, y, 1);
}
}
int main(){
scanf("%d", &T);
while(T--){
init();
read();
printf("%d\n", solve());
}
return 0;
}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 207;
const int maxm = 30007;
const int inf = 0x3f3f3f3f;
int n, m;
int minD, cntx, cnty, edge[maxn][maxn];
bool visx[maxn], visy[maxn];
int linkx[maxn], link[maxn], wx[maxn], wy[maxn];
bool dfs(int x){ //匈牙利算法找增广路径
visx[x] = true;
for(int i = 1; i <= cnty; i++){
if(!visy[i]){
int t = wx[x] + wy[i] - edge[x][i];
if(t == 0) {
visy[i] = true;
if(link[i] == 0 || dfs(link[i])){
linkx[x] = i;
link[i] = x;
return true;
}
}
else if(t > 0){ //找出边权与顶标和的最小的差值
if(t < minD){
minD = t;
}
}
}
}
return false;
}
int km(){
memset(linkx, 0, sizeof linkx); //linkx[i]表示与X部中点i匹配的点
memset(link, 0, sizeof link);
memset(wy, 0, sizeof(wy));
for(int i = 1; i <= cntx; i++){
wx[i] = -inf;
for(int j = 1; j <= cnty; j++){
if(wx[i] < edge[i][j]){
wx[i] = edge[i][j];//初始化为权值最大的边的权值
}
}
}
for(int i = 1; i <= cntx; i++){
while(1){
minD = inf;
memset(visx, false, sizeof visx);
memset(visy, false, sizeof visy);
if(dfs(i)){
break;
}
for(int j = 1; j <= cntx; j++){ //将交错树中X部的点的顶标减去minz
if(visx[j]){
wx[j] -= minD;
}
}
for(int j = 1; j <= cnty; j++){ //将交错树中Y部的点的顶标加上minz
if(visy[j]){
wy[j] += minD;
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnty; i ++){
if(link[i]!=0){
ans += edge[link[i]][i];
}
}
return ans;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
cntx = cnty = n;
memset(edge, 0, sizeof(edge));
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[u][v] = max(edge[u][v], w);
}
printf("%d\n", km());
}
return 0;
}

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
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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 207;
const int maxm = 30007;
const int inf = 0x3f3f3f3f;
int n, m;
int minD, cntx, cnty, edge[maxn][maxn];
bool visx[maxn], visy[maxn];
int linkx[maxn], link[maxn], wx[maxn], wy[maxn];
bool dfs(int x){ //匈牙利算法找增广路径
visx[x] = true;
for(int i = 1; i <= cnty; i++){
if(!visy[i]){
int t = wx[x] + wy[i] - edge[x][i];
if(t == 0) {
visy[i] = true;
if(link[i] == 0 || dfs(link[i])){
linkx[x] = i;
link[i] = x;
return true;
}
}
else if(t > 0){ //找出边权与顶标和的最小的差值
if(t < minD){
minD = t;
}
}
}
}
return false;
}
int km(){
memset(linkx, 0, sizeof linkx); //linkx[i]表示与X部中点i匹配的点
memset(link, 0, sizeof link);
memset(wy, 0, sizeof(wy));
for(int i = 1; i <= cntx; i++){
wx[i] = -inf;
for(int j = 1; j <= cnty; j++){
if(wx[i] < edge[i][j]){
wx[i] = edge[i][j];//初始化为权值最大的边的权值
}
}
}
for(int i = 1; i <= cntx; i++){
while(1){
minD = inf;
memset(visx, false, sizeof visx);
memset(visy, false, sizeof visy);
if(dfs(i)){
break;
}
for(int j = 1; j <= cntx; j++){ //将交错树中X部的点的顶标减去minz
if(visx[j]){
wx[j] -= minD;
}
}
for(int j = 1; j <= cnty; j++){ //将交错树中Y部的点的顶标加上minz
if(visy[j]){
wy[j] += minD;
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnty; i ++){
if(link[i]!=0&&edge[link[i]][i]!=-inf){
ans += edge[link[i]][i];
}
}
return -ans;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
cntx = cnty = n;
for(int i = 0; i <= cntx; i++){
for(int j = 0; j <= cnty; j++){
edge[i][j] = -inf;
}
}
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[u][v] = max(edge[u][v], -w);
}
printf("%d\n", km());
}
return 0;
}

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
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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 207;
const int maxm = 30007;
const int inf = 0x3f3f3f3f;
int n, m;
int minD, cntx, cnty, edge[maxn][maxn];
bool visx[maxn], visy[maxn];
int linkx[maxn], link[maxn], wx[maxn], wy[maxn];
bool dfs(int x){ //匈牙利算法找增广路径
visx[x] = true;
for(int i = 1; i <= cnty; i++){
if(!visy[i]){
int t = wx[x] + wy[i] - edge[x][i];
if(t == 0) {
visy[i] = true;
if(link[i] == 0 || dfs(link[i])){
linkx[x] = i;
link[i] = x;
return true;
}
}
else if(t > 0){ //找出边权与顶标和的最小的差值
if(t < minD){
minD = t;
}
}
}
}
return false;
}
int km(){
memset(linkx, 0, sizeof linkx); //linkx[i]表示与X部中点i匹配的点
memset(link, 0, sizeof link);
memset(wy, 0, sizeof(wy));
for(int i = 1; i <= cntx; i++){
wx[i] = -inf;
for(int j = 1; j <= cnty; j++){
if(wx[i] < edge[i][j]){
wx[i] = edge[i][j];//初始化为权值最大的边的权值
}
}
}
for(int i = 1; i <= cntx; i++){
while(1){
minD = inf;
memset(visx, false, sizeof visx);
memset(visy, false, sizeof visy);
if(dfs(i)){
break;
}
for(int j = 1; j <= cntx; j++){ //将交错树中X部的点的顶标减去minz
if(visx[j]){
wx[j] -= minD;
}
}
for(int j = 1; j <= cnty; j++){ //将交错树中Y部的点的顶标加上minz
if(visy[j]){
wy[j] += minD;
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnty; i ++){
if(link[i]!=0&&edge[link[i]][i]!=-inf){
ans += edge[link[i]][i];
}
}
return -ans;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
cntx = cnty = n;
for(int i = 0; i <= cntx; i++){
for(int j = 0; j <= cnty; j++){
edge[i][j] = -inf;
}
}
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[u][v] = max(edge[u][v], -w);
}
printf("%d\n", km());
}
return 0;
}

强连通

Tarjan

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
int n, m;
int head[maxn], cnt, top, dfs_num, col_num;
int dfn[maxn], low[maxn], Stack[maxn], color[maxn];
bool vis[maxn];
struct EDGE{
int next, to, u;
}edge[maxn<<3];
void add(int u, int v){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].u = u;
head[u] = cnt++;
}
void Tarjan(int x){
dfn[x] = ++dfs_num;
low[x] = dfs_num;
vis[x] = true; //是否在栈中
Stack[++top] = x;
for(int i = head[x]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v]){
low[x] = min(low[x], dfn[v]);
}
}
if(dfn[x] == low[x]){ //构成强连通分量
vis[x] = false;
color[x] = ++col_num; //染色
while(Stack[top] != x){ //清空
color[Stack[top]] = col_num;
vis [ Stack[ top-- ] ] = false ;
}
top--;
}
}
void init(){
top = dfs_num = col_num = cnt = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(color, 0, sizeof(color));
memset(vis, false, sizeof(vis));
}
void read(){
int u, v;
for(int i = 0; i < m; i++){
scanf("%d%d", &u, &v);
add(u, v);
}
}
void solve(){
for(int i = 1; i <= n; i++){
if(!color[i]){
Tarjan(i);
}
}
if(col_num != 1){
printf("No\n");
}
else{
printf("Yes\n");
}
}
int main(){
while(~scanf("%d%d", &n, &m) && n+m){
init();
read();
solve();
}
return 0;
}

数论

gcd

1
2
3
int gcd(int a, int b){
return !b ? a : gcd(b, a%b);
}

快速乘

如果要求模的常数是一个64bit整数,那么在做乘法时,就没有扩展类型使用,必须手写一个高精度整数运算。

O(logn)快速乘

1
2
3
4
5
6
7
8
9
inline LL quick_mul(LL a,LL n,LL m){
LL ans=0;
while(n){
if(n&1) ans=(ans+a)%m;
a=(a<<1)%m;
n>>=1;
}
return ans;
}

O(1)快速乘

1
2
3
4
5
6
7
8
typedef long long ll;
#define MOL 123456789012345LL
inline ll mul_mod_ll(ll a,ll b){
ll d=(ll)floor(a*(long double)b/MOL+0.5);
ll ret=a*b-d*MOL;
if(ret<0) ret+=MOL;
return ret;
}

首先,使用浮点数计算 ab/MOL 的值,关键在于第二句,显然 ab - d*MOL 两个乘法都可能溢出,不过没关系,因为可以预见,其差是一个64bit可以容纳的正整数,那么溢出部分的差仅可能是0或者1。最后一句符号的特判用来处理溢出部分差为1的情况。

考虑到计算 a*b/MOL 使用了浮点数计算,误差是不可避免的,故建议不要用太大的MOL使用这个方法。

模板

1
2
3
inline ll ksc(ll x,ll y,ll mod){
return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}

因为x,y都是mod意义下的,保证了x*y/mod不会爆long long。

其他

离散化

1
2
3
4
5
6
7
8
int getid(int x){
return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
for(int i = 1;i<=n;++i){
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end()), v.erase(unique(v.begin(),v.end()),v.end());

位运算

统计1的个数

1
2
3
4
5
6
7
8
int NumberOfOne(int n) {
int count = 0;
while(n) {
n &= (n-1);
count++;
}
return count;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!