0%

ACM

发表于 更新于 阅读次数：

ACM个人模板整理

咕咕咕~

图论前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define ll long long
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
struct edge{
    int to, next;
    ll w;
}e[maxm];
int head[maxn], num;
void add(int u, int v, int w=0){
    e[num] = (edge){v, head[u],w};head[u] = num++;
    //e[num] = (edge){u, head[v],w};head[v] = num++; // 反向边
}
void init(){
    memset(head,-1;sizeof head);
    num = 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
/*
单源最短路常用模板
dijkstra+堆优化， 非堆优化太丑，不写

只能跑正权图
复杂度 O(mlogm) m为边数
*/

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mk(a,b) make_pair(a,b)
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
struct edge{
    int to, next, w;
}e[maxm];
int head[maxn], num;
void add(int u, int v, int w){
    e[num] = (edge){v, head[u], w}; head[u] = num++;
}
int d[maxn];
void dijkstra(int st){
    memset(d, 0x3f, sizeof d);
    d[st] = 0;
    priority_queue<pair<int,int> > q;
    q.push(mk(0,st));
    while(!q.empty()){
        int u = q.top().second;
        int dd = -q.top().first;
        q.pop();
        if(dd != d[u]) continue;
        for(int i=head[u];~i;i=e[i].next){
            int v = e[i].to;
            if(d[v] > d[u] + e[i].w){
                d[v] = d[u] + e[i].w;
                q.push(mk(-d[v], v)); // 优先队列大根堆压入负值
            }
        }
    }
}
int main(){
    num = 0;
    memset(head, -1, sizeof head);
    // 建图
    dijkstra();
    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
/*
单源最短路常用模板
正权图、负权图都能跑，可以判断负环
复杂度 O(km) m为边数、k为每个点平均入队次数(常数)
*/

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
struct edge{
    int to, next, w;
}e[maxm];
int head[maxn], num;
void add(int u, int v, int w){
    e[num] = (edge){v, head[u], w}; head[u] = num++;
}
int d[maxn];
bool vis[maxn];
void spfa(int st){
    memset(d, 0x3f, sizeof d);
    memset(vis, 0, sizeof vis);
    d[st] = 0;
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=head[u];~i;i=e[i].next){
            int v = e[i].to;
            if(d[v] > d[u] + e[i].w){
                d[v] = e[i].w + d[u];
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    num = 0;
    memset(head, -1, sizeof head);
    // 建图
    spfa();
    return 0;
}

floyd

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
/*
多源最短路
复杂度 O(n^3) n点数

*/
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e3 + 5;
int mp[maxn][maxn]
int d[maxn];
int n;
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]);
            }
        }
    }
}
int main(){
    // 建图
    floyd();
    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
int dfn[maxn], low[maxn];
int vis[maxn], id;
int cnt, scc[maxn];
stack<int> s;
void tarjan(int u){
	dfn[u] = low[u] = ++id;
    s.push(u);
    vis[u] = 1;
    for(int i=head[u];~i;i=e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[v], low[u]);
        }
        else if(vis[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        cnt++;
        while(1){
            int v = s.top();
            scc[v] = cnt;
            vis[v] = 0;
            s.pop();
            if(v == u) break;
        }
    }
}

求割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfn[maxn], low[maxn];
int id, cnt;
int vis[maxn]; // 标记点是不是割点
void tarjan(int u， int root){
	dfn[u] = low[u] = ++id;
    int son = 0;
    for(int i=head[u];~i;i=e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v, root);
            if(u != root && dfn[u] <= low[v]) vis[u] = 1;            
            low[u] = min(low[v], low[u]);
        }
        else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(u==root && son > 1) vis[u] = 1;
}

求桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfn[maxn], low[maxn];
int id, cnt;
int vis[maxm]; // 标记边是不是割边
void tarjan(int u， int root){
	dfn[u] = low[u] = ++id;
    int son = 0;
    for(int i=head[u];~i;i=e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v, root);
            // 若有重边，需要特殊判断。
            if(dfn[u] < low[v]) vis[i] = vis[i^1] = 1; // 双向边            
            low[u] = min(low[v], low[u]);
        }
        else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

最小生成树

kruskal

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
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
struct edge{
    int to, next, w;
    bool operator < (const edge&hs) const{
        return w < hs.w;
    }
}e[maxm];
int head[maxn], num;
int n;
void add(int u, int v, int w){
    e[num] = (edge){v, head[u], w}; head[u] = num++;
}
int pre[maxn];
int fin(int x){ return x == pre[x]?x:pre[x]=fin(pre[x]); }
bool merge(int x, int y){
    int fx = fin(x), fy = fin(y);
    if(fx == fy) return 0;
    pre[fx] = fy;
    return 1;
}

int main(){
    num = 0;
    memset(head, -1, sizeof head);
    for(int i=1;i<=n;i++) pre[i] = i;
    // 建图
    int sum = 0, cnt = 0;
    for(int i=0;i<num;i+=2){
        if(merge(e[i].to, e[i+1].to)){
            sum += e[i].w;
            if(++cnt == n-1) break; 
        }
    }
    if(cnt != n) puts("没有最小生成树");
    else printf("%d\n", sum);
    return 0;
}

二分图匹配

Hungary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int link[maxn];
int used[maxn];
bool dfs(int u){
    for(int i=head[u];~i;i=e[i].next){
        int v = e[i].to;
        if(used[v]) continue;
        if(link[v] == -1 || dfs(link[v])){
            link[v] = u;
            return 1;
        }
    }
    return 0;
}
int Hungary(){
    int ans = 0;
    memset(link, -1, sizeof link);
    
    for(int i=1;i<=n;i++){
    	memset(used, 0, sizeof used);
        if(dfs(i)) ans++;
    }
}

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
int sx[maxn],sy[maxn];
int ux[maxn],uy[maxn];
int slack[maxn],link[maxn],n,ans,m,mp[maxn][maxn];
bool dfs(int u)
{	
	ux[u] = 1;
	for(int v=1;v<=n;v++){
		int cnt = sx[u]+sy[v]-mp[u][v];
		if(cnt==0&&!uy[v]){
			uy[v]=1;
			if(link[v]==-1||dfs(link[v])){
				link[v] = u;
				return true;
			}
		}
		else {
			slack[v] = min(slack[v],cnt);
		}
	}
	return false;
}
void update()
{
	int a = inf;
	for(int i=1;i<=n;i++)
		if(!uy[i])
			a = min(a,slack[i]);
	for(int j=1;j<=n;j++){
		if(ux[j]) sx[j]-=a;
		if(uy[j]) sy[j]+=a;
	}
}
void km()
{
	memset(sx, 0, sizeof sx);
    memset(sy, 0, sizeof sy);
    memset(link,-1,sizeof link);
	ans = 0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(sx[i]==0||sx[i]<mp[i][j]) sx[i] = mp[i][j]; 
	for(int i=1;i<=n;i++){
		memset(slack, 0x3f, sizeof slack);
		while(1){
			memset(ux, 0, sizeof ux);
    		memset(uy, 0, sizeof uy);
			if(dfs(i)) break;
			update();
		} 
	}
	int i;
	for(i=1;i<=n;i++){
		if(link[i]==-1||sx[i]==-inf||sy[i]==-inf) break;
		ans += sx[i]+sy[i];
	}
	if(i>n) printf("%d\n",ans);
	else puts("-1");
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int d[maxn], cnt;
void Topo(){
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q.push(i);
   	while(!q.empty()){
        int u = q.front();
        q.pop();
        cnt++;
        for(int i=head[u];~i;i=e[i].next){
            if(-- d[e[i].to] == 0) q.push(e[i].to);
        }
    }
    
}

网络流

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
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
struct edge{
    int to, next, w;
}e[maxm];
int head[maxn], num;
int n;
void add(int u, int v, int w){
    e[num] = (edge){v, head[u], w}; head[u] = num++;
    e[num] = (edge){u, head[v], 0}; head[v] = num++; 
}
int st, ed;
int d[maxn];
bool bfs(){
    memset(d, -1, sizeof d);
    d[st] = 1;
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].next){
            int v = e[i].to;
            if(d[v] > 0 || e[i].w == 0 ) continue;
            d[v] = d[u] + 1;
            if(v == ed) return 1;
            q.push(v);
        }
    }
    return 0;
}
int cur[maxn];
int dfs(int u, int exp){
    if(u == ed || !exp) return exp;
    int flow = 0, f;
    for(int& i=cur[u];~i;i=e[i].next){
        int v = e[i].to;
        if(d[v] == d[u] + 1 && (f=dfs(v, min(exp, e[i].w)))){
            e[i].w -= f;
            e[i^1].w += f;
            flow += f;
            exp -= f;
            if(!exp) break;
        }
    }
    return flow;
}

int dinic(){
    int ans = 0;
    while(bfs()){
        memcpy(cur, head, sizeof head);
        ans += dfs(st, inf);
    }
    return ans;
}
int main(){
    num = 0;
    memset(head, -1, sizeof head);
    // 建图
    printf("%d\n", dinic());
    return 0;
}