算法模板

xiaoxiao2021-02-28  17

武林秘籍

头文件

#include<set> #include<cmath> #include<cstring> #include<map> #include<algorithm> #include<map> #include<sstream> #include<iostream> #include<functional> const int inf = 0x3f3f3f3f; #define inf 0x3f3f3f3f

素数筛选

//埃氏筛法 int prime[MAXNUM]; //第i个素数 bool isPrime[MAXNUM + 1]; //isPrime[i]为true表示i为素数 //返回n以内的素数个数 int sieve(int n){ int p = 0; fill(isPrime, isPrime + n + 1, true); isPrime[0] = isPrime[1] = false; for(int i = 2; i <= n; i++){ if(isPrime[i]){ prime[p++] = i; for(int j = 2*i; j <= n; j += i) isPrime[j] = false; } } return p; }

快速幂

typedef long long ll; ll modPow(ll x, ll n, ll mod){ ll res = 1; while(n > 0){ if(n & 1) res = res*x%mod; // 判断是否为奇数,若是则true x = x*x%mod; n >>= 1; } return res; }

GCD

//辗转相除法 int GCD(int a, int b){ return b == 0 ? a : GCD(b, a % b); }

全排列

bool visit[MAXNUM]; int perm[MAXNUM]; void permutation(int pos, int n){ if(pos == n){ /* 这里对perm[]操作 */ return ; } for(int i = 0; i < n; i++){ if(visit[i] == false){ visit[i] = true; permutation(pos + 1, n); visit[i] = false; } } } //在c++的标准库中已经集成了next_permutation() do{ /* 这里是对perm[]的操作 */ } while(next_permutation(perm, perm + n));

二分查找

// left为最开始元素, right是末尾元素的下一个数,x是要找的数 int bsearch(int *A, int left, int right, int x){ int m; while (left < right){ m = left + (right - left) / 2; if (A[m] >= x) right = m; else left = m + 1; // 如果要替换为 upper_bound, 改为:if (A[m] <= v) x = m+1; else y = m; } return left; } /* 最后left == right 如果没有找到135577找6,返回7 如果找有多少的x,可以用lower_bound查找一遍,upper_bound查找一遍,下标相减 C++自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址 upper_bound(a,a+n,x)返回数组中第一个x的地址 如果a+n内没有找到x或x的下一个地址,返回a+n的地址 lower_bound(a,a+n,x)-upper_bound(a,a+n,x)返回数组中x的个数 */

并查集

int findFather(int x){ return x == father[x] ? x : findFather(x); // if(x == father[x]) // return x; // else{ //压缩路径 // father[x] = findFather(x); // return father[x]; } } int merge(int v, int u){ v = findFather(v); u = findFather(u); if(u != v){ father[u] = v; return 1; } return 0; }

Dijkstra(单源最短路径)

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510], dis[510]; bool visit[510]; int n, m; int main(){ fill(e[0], e[0] + 510*510, inf); fill(dis, dis + 510, inf); scanf("%d%d", &n, &m); int a, b, c; for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &c); e[a][b] = e[b][a] = c; } dis[1] = 0; for(int i = 0; i < n; i++){ int u = -1, minn = inf; for(int j = 1; j <= n; j++) if(visit[j] == false && dis[j] < minn){ minn = dis[j]; u = j; } if(u == -1) break; visit[u] = true; for(int v = 1; v <= n; v++) if(visit[v] == false && e[u][v] != inf){ if(dis[v] > dis[u] + e[u][v]) dis[v] = dis[u] + e[u][v]; } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); return 0; }

SPFA(单源最短路径解决负权)

写法一

#include<iostream> #include<algorithm> #include<queue> using namespace std; const int inf = 0x3f3f3f3f; int dis[510], head[510]; bool visit[510]; int n, m, cnt; struct node{ int u, v, w; int next; }e[510]; void add(int u, int v, int w){ e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt++; } int main(){ fill(dis, dis + 510, inf); fill(head, head + 510, -1); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); add(u, v, w); } dis[1] = 0; visit[1] = true; queue<int> q; q.push(1); while(!q.empty()){ u = q.front(); q.pop(); visit[u] = false; for(int i = head[u]; i != -1; i = e[i].next){ v = e[i].v; w = e[i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; if(visit[v] == false) visit[v] = true, q.push(v); } } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); }

写法二

#include<iostream> #include<map> #include<queue> #include<vector> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; vector<pair<int, int> > e[510]; queue<int> q; int dis[510]; bool visit[510]; int main(){ int n, m; fill(dis, dis + 510, inf); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); e[u].push_back(make_pair(v, w)); } visit[1] = true; dis[1] = 0; q.push(1); while(!q.empty()){ u = q.front(); q.pop(); visit[u] = false; for(int i = 0; i < e[u].size(); i++){ v = e[u][i].first; w = e[u][i].second; if(dis[u] + w < dis[v]){ dis[v] = dis[u] + w; if(visit[v] == false) visit[v] = false, q.push(v); } } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); return 0; }

Floyed

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510]; int n, m; int main(){ fill(e[0], e[0] + 510*510, inf); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); e[u][v] = e[v][u] = w; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) printf("%d%c", e[i][j], j == n ? '\n' : ' '); return 0; }

Prim(最小生成树)

#include<iostream> #include<algorithm> using namespace std; struct node{ int u, v, w; bool friend operator < (const node &a, const node &b){ return a.w < b.w; } }e[510]; int n, m; int father[510]; int findFather(int x){ return x == father[x] ? x : father[x] = findFather(father[x]); } int merge(int x, int y){ x = findFather(x); y = findFather(y); if(x != y){ father[x] = y; return 1; } return 0; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) father[i] = i; for(int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); sort(e, e + m); int sum = 0, cnt = 0; for(int i = 0; i < m; i++){ if(merge(e[i].u, e[i].v)){ cnt++; sum += e[i].w; } if(cnt == n - 1) break; } printf("%d\n", sum); return 0; }

kruskal(最小生成树)

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510], dis[510]; bool visit[510]; int main(){ int n ,m; scanf("%d%d", &n, &m); int a, b, c; fill(dis, dis + 510, inf); fill(e[0], e[0] + 510*510, inf); for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &c); e[a][b] = e[b][a] = c; } dis[1] = 0; int sum = 0; for(int i = 0; i < n; i++){ int u = -1, minn = inf; for(int j = 1; j <= n; j++){ if(visit[j] == false && dis[j] < minn){ minn = dis[j]; u = j; } } if(u == -1) break; sum += minn; visit[u] = true; for(int v = 1; v <= n; v++) if(visit[v] == false && dis[v] > e[u][v]){ dis[v] = e[u][v]; } } printf("%d\n", sum); return 0; }

线段树(区间和,修改区间,区间最大最小)

#include<iostream> #include<algorithm> using namespace std; struct node{ int l, r, max, sum; int mild(){ return (l + r)>>1; } }T[510]; int n, m; void up(int root){ T[root].sum = T[root<<1].sum + T[root<<1|1].sum; T[root].max = max(T[root<<1].max, T[root<<1|1].max); } void build(int l, int r, int root){ T[root].l = l, T[root].r = r; if(l == r){ int temp; scanf("%d", &temp); T[root].max = T[root].sum = temp; } int mild = T[root].mild(); build(l, mild, root<<1); build(mild + 1, r, root<<1|1); up(root); } void update(int root, int pos, int num){ if(T[root].l == T[root].r && T[root].r == pos){ T[root].max = T[root].sum = num; return; } int mild = T[root].mild(); if(pos <= mild) update(root<<1, pos, num); else update(root<<1|1, pos, num); up(root); } int getSum(int l, int r, int root){ if(l == T[root].l && r == T[root].r) return T[root].sum; int mild = T[root].mild(); if(r <= mild) return getSum(l, r, root<<1); else if(l > mild) return getSum(l, r, root<<1|1); else return getSum(l, mild, root<<1) + getSum(mild + 1, r, root<<1|1); } int getMax(int l, int r, int root){ if(l == T[root].l && r == T[root].r) return T[root].max; int mild = T[root].mild(); if(r <= mild) return getMax(l, r, root<<1); else if(l > mild) return getSum(l, r, root<<1|1); else return max(getMax(l, mild, root<<1), getMax(mild + 1, r, root<<1|1)) } int main(){ scanf("%d%d", &n, &m); build(1, n, 1); while(m--){ int x, y, p; scanf("%d%d%d", &p, &x, &y); if(p == 1) update(x, 1, y); else if(p == 2) printf("%d\n", getSum(x,y,1)); else printf("%d\n", getMax(x,y,1)); } return 0; }

主席树(区间第K大问题)

#include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 1e5 + 7; int root[N], a[N], cnt, x, y, k, n, m; struct node{ int l, r, sum; }T[40*N]; vector<int> v; int getid(int x){ return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int l, int r, int &x, int y, int pos){ T[++cnt] = T[y], T[cnt].sum++, x = cnt; if(l == r) return; int mild = (l + r)>>1; if(pos <= mild) update(l, mild, T[x].l, T[y].l, pos); else update(mild + 1, r, T[x].r, T[y].r, pos); } int query(int l, int r, int x, int y, int k){ if(l == r) return l; int sum = T[T[y].l].sum - T[T[x].l].sum; int mild = (l + r)>>1; if(k <= sum) return query(l, mild, T[x].l, T[y].l, k); else return query(mild + 1, r, T[x].r, T[y].r, k - sum) } int main(){ scanf("%d%d", &n, &m); 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()); for(int i = 1; i <= n; i++) update(1, n, root[i], root[i - 1], getid(a[i])); for(int i = 0; i < m; i++){ scanf("%d%d%d", &x, &y, &k); printf("%d\n", v[query(1, n, root[x - 1], root[y], k) - 1]); } return 0; }

树状数组(区间第K大问题)

//HDU 5249 http://acm.hdu.edu.cn/showproblem.php?pid=5249 //数据过大需要采用离散化。 #include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 1e5 + 10; #define lowbit(x) (x & -x) int c[N], a[N]; char str[N][10]; vector<int> v; int n, m; int getid(int x){ return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int x, int val){ for(int i = x; i <= n; i += lowbit(i)) c[i] += val; } int getsum(int x){ int sum = 0; for(int i = x; i >= 1; i -= lowbit(i)) sum += c[i]; return sum; } int solve(int x){ int left = 1, right = n, mid; int k = x / 2 + 1; while(left < right) { mid = (left + right) / 2; if(getsum(mid) >= k) right = mid; else left = mid + 1; } return left; } int main(){ int T = 1, x; while(~scanf("%d", &m)){ queue<int> q; memset(c, 0, sizeof(c)), v.clear(); for(int i = 1; i <= m; ++i){ scanf("%s", str[i]); if(str[i][0] == 'i'){ scanf("%d", &a[i]); v.push_back(a[i]); } } sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()); n = v.size(); printf("Case #%d:\n",T++); for(int i = 1; i <= m; ++i){ if(str[i][0] == 'i'){ x = getid(a[i]); update(x, 1); q.push(x); }else if(str[i][0] == 'o'){ x = q.front(); update(x, -1); q.pop(); }else{ printf("%d\n", v[solve(q.size()) - 1]); } } } return 0; }

树状数组(区间和)

#include<iostream> using namespace std; int tree[510]; int n; int lowbit(int x){ return x & (-x); } void update(int x, int num){ while(x <= n){ tree[x] += num; x = lowbit(x); } } int getSum(int x){ int sum = 0; while(x > 0){ sum += tree[x]; x -= lowbit(x); } return sum; } int main(){ scanf("%d", &n); int temp; for(int i = 1; i <= n; i++){ scanf("%d", &temp); update(i, temp); } return 0; }

凸包

#include<iostream> #include<algorithm> #include<cmath> #include<vector> #define N 105 using namespace std; struct node{ int x, y; bool friend operator < (const node &a, const node &b){ if(a.y == b.y) return a.x < b.x; return a.y < b.y; } }point[N]; double calcurateDis(node a, node b){ return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } bool judge(node a, node b, node c){ return (a.x - c.x)*(b.y - c.y) >= (b.x - c.x)*(a.y - c.y); } double solve(int n){ vector<node> tempPoint(n*2); sort(point, point + n); if(n == 1){ return 0; } if(n == 2){ return calcurateDis(point[0], point[1]); } tempPoint[0] = point[0]; tempPoint[1] = point[1]; tempPoint[2] = point[2]; int top = 1; for(int i = 2; i < n; i++){ while(top != 0 && judge(point[i], tempPoint[top], tempPoint[top - 1])) top--; tempPoint[++top] = point[i]; } int len = top; tempPoint[++top] = point[n - 2]; for(int i = n - 3; i >= 0; i--){ while(top != len && judge(point[i], tempPoint[top], tempPoint[top - 1])) top--; tempPoint[++top] = point[i]; } double result = 0.0; for(int i = 0; i < top; i++){ result += calcurateDis(tempPoint[i], tempPoint[i + 1]); } return result; } int main(){ int n; while(~scanf("%d", &n), n){ for(int i = 0; i < n; i++) scanf("%d %d", &point[i].x, &point[i].y); printf("%.2lf\n", solve(n)); } return 0; }

二分图(最佳完备匹配)

#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int inf = 0x3f3f3f3f; const int N = 105; int e[N][N], line[N], cx[N], cy[N]; bool usex[N], usey[N]; int n, m; int find(int x){ usex[x] = true; for(int i = 1; i <= m; i++) if(usey[i] == false && cx[x] + cy[i] == e[u][i]){ usey[i] = true; if(line[i] == 0 || find(line[i])){ line[i] = x; return 1; } } return 0; } int KM(){ for(int i = 1; i <= n; i++){ while(true){ memset(usex, 0, sizeof(usex)); memset(usey, 0, sizeof(usey)); if(find(i)) break; int d = inf; for(int j = 1; j <= n; j++){ if(usex[j]) for(int k = 1; k <= m; k++){ if(usey[k] == false) d = min(d, cx[j] + cy[k] - e[j][k]); } } if(d == inf) return -1; for(int j = 1; j <= n; j++) if(usex[j]) cx[j] -= d; for(int j = 1; j <= m; j++) if(usey[j]) cy[j] += d; } } int sum = 0; for(int i = 1; i <= m; i++) sum += e[line[i]][i]; return sum; } int main(){ while(~scanf("%d%d", &n, &m)){ memset(cy, 0, sizeof(cy)); memset(e, 0, sizeof(e)); memset(cx, 0, sizeof(cx)); for(int i = 1; i <= n; i++){ int d = 0; for(int j = 1; j <= n; j++){ scanf("%d", &e[i][j]); d = max(d, e[i][j]); } cx[i] = d; } memset(line, 0, sizeof); peintf("%d\n", KM()); } return 0; }

最大流Dinic

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <map> #include <queue> #include <vector> using namespace std; const int N = 1100; const int INF = 0x3f3f3f3f; struct Node { int to;//终点 int cap; //容量 int rev; //反向边 }; vector<Node> v[N]; //图的邻接表表示 int level[N]; //顶点到源点的距离标号 int iter[N]; //当前弧,在其之前的边已经没用了 // 向图中增加一条from到to的容量为cap的边 void add_Node(int from,int to,int cap) //重边情况不影响 { v[from].push_back((Node){to,cap,v[to].size()}); v[to].push_back((Node){from,0,v[from].size()-1}); } //通过BFS计算从源点出发的距离标号 void bfs(int s){ memset(level, -1, sizeof(level)); queue<int> que; level[s] = 0; que.push(s); while(!que.empty()){ int t = que.front(); que.pop(); for(int i = 0; i < v[t].size(); i++){ Node &e = v[t][i]; if(e.cap > 0 && level[e.to] < 0){ level[e.to] = level[t] + 1; que.push(e.to); } } } } //通过DFS寻找曾广路 int dfs(int s, int t, int f) { if(s==t) return f; for(int &i= iter[s]; i<v[s].size() ; i++) { Node &e = v[s][i]; if(level[s] < level[e.to] && e.cap>0) { int d=dfs(e.to, t, min(f,e.cap)); if(d>0) { e.cap -= d; v[e.to][e.rev].cap += d; return d; } } } return 0; } //求解s到t的最大流 int max_flow(int s, int t) { int flow=0; for(;;){ bfs(s); if(level[t] < 0) return flow; memset(iter,0,sizeof(iter)); int f; while((f = dfs(s, t, INF)) > 0) flow+=f; } } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { memset(v,0,sizeof(v)); for(int i=0;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add_Node(x,y,z); } printf("%d\n",max_flow(1,m)); } }

最小费用

//Bellman—Ford算法 //Bellman算法求最短增广路&最小费用流 O(FEV) #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int N = 100; typedef pair<int, int> P; struct node{ int to; int cap; int cost; int rev; }; vector<node> G[N]; int dis[N]; //单源点s到其它顶点的最短距离(本次搜索的最小费用) int prevv[N]; //最短路中的前驱结点 对应边 int preve[N]; int addNOde(int from, int to, int cap, int cost){ G[from].push_back((node){to, cap, cost, G[to].size()}); G[to].push_back((node){from, 0, - cost, G[from].size() - 1}); } int V; int min_cost_flow(int s, int t, int f){ int ret = 0; while(f > 0){ fill(dis, dis + N, INF); dis[s] = 0; bool update = true; while(update){ //bellman算法求解s-t可达路径中的最短路(费用最少)且是否可达由e.c是否大于0决定 update = false; for(int i = 0; i < V; ++i){ if(dis[i] == INF) continue; for(int j = 0; j < G[i].size(); ++j){ node &e = G[i][j]; if(e.cap > 0 && dis[e.to] > dis[i] + e.cost){ dis[e.to] = dis[i] + e.cost; prevv[e.to] = i; //路径还原 preve[e.to] = j; } } } } if(dis[t] == INF) return -1; int d = f; //d:本次求得的最小费用流 for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap); ret += d * dis[t]; f -= d; for(int v = t; v != s; v = prevv[v]){ node &e = G[prevv[v]][preve[v]]; e.cap -= d; G[e.to][e.rev] += d; } } return ret; } //最小费用流Dijkstra算法 //Dijkstra算法求最小费用流核心代码: //h[MAX_V]:导入势保证所有边均为非负边 O(FElogV) int min_cost_flow(int s, int t, int f){ int ret = 0; memset(h, 0, sizeof(h)); while(f > 0){ priority_queue<P, vector<P>, greater<P> > q; fill(dis, dis + N, INF); dis[s] = 0; q.push(P(0, s)); while(!q.empty()){ P p = q.top(); q.pop(); int v = p.second; if(dis[v] < p.second) continue; for(int i = 0; i < G[v].size(); ++i){ node &e = G[v][i]; if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){ dis[e.to] = dis[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; q.push(P(dis[e.to], e.to)); } } } if(dis[t] == INF) return -1; for(int v = 0; v < V; ++v) h[v] += dis[v]; int d = f; for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap); ret += h[t] * d; f -= d; for(int v = t; v != s; v = prevv[v]){ node &e = G[prevv[v]][preve[v]]; e.cap -= d; G[e.to][e.rev] += d; } } return ret; }
转载请注明原文地址: https://www.6miu.com/read-1600294.html

最新回复(0)