在此整理了一些ACM比赛中常用的算法模板,不定期更新,都是以前写的,现在看起来有些细节的风格都不一样。

树状数组
int bit[1048576], N;

inline int lowbit(int x)
{
    return x & (-x);
}

void add(int p, int x)
{
    for (int i = p; i <= N; i += lowbit(i)) {
        bit[i] += x;
    }
}

int sum(int p)
{
    int res = 0;
    for (int i = p; i > 0; i -= lowbit(i)) {
        res += bit[i];
    }
    return res;
}
 
最小生成树
Kruskal
const int maxn = 1024;
const int maxe = 20005;
struct Edge {
        int u, v, c;
}edge[maxe];
int ra[maxe], pa[maxn], N, M;
 
int cmp(int a, int b)
{
        return edge[a].c > edge[b].c;
}
 
int findp(int x)
{
        return x==pa[x] ? x : pa[x]=findp(pa[x]);
}
 
int kruskal()
{
        int ret = 0;
        for(int i=0; i<=N; i++) pa[i] = i;
        for(int i=0; i<M; i++) ra[i] = i;
        sort(ra, ra+M, cmp);
        for(int i=0; i<M; i++) {
                int t = ra[i];
                int x = findp(edge[t].u);
                int y = findp(edge[t].v);
                if(x!=y) {
                        pa[x] = y;
                        ret += edge[t].c;
                }
        }
        return ret;
}
单源最短路
struct Edge {
    int u, v, w;
    Edge(int u, int v, int w):
        u(u), v(v), w(w) {}
};
vector<Edge> G[maxv];
int dis[maxv];
typedef pair<int, int> P;
 
int dijkstra(int from, int to)
{
    priority_queue<P, vector<P>, greater<P> > pq;
    memset(dis, 0x3f, sizeof(dis));
    pq.push(P(0, from));
    dis[from] = 0;
    while(!pq.empty()) {
        P p = pq.top(); pq.pop();
        int u = p.second;
        if(u == to)
            return dis[to];
        if(p.first > dis[u])
            continue;
        for(int i = 0; i < G[u].size(); i++) {
            Edge e = G[u][i];
            if(dis[u] + e.w < dis[e.v]) {
                dis[e.v] = dis[u] + e.w;
                pq.push(P(dis[e.v], e.v));
            }
        }
    }
    return dis[to];
}
 
 
网络流
const int maxn = 1024;
const int INF = 0x3f3f3f3f;
 
struct Edge {
        int to, cap, next;
};
 
Edge edge[maxn*50];
int level[maxn], iter[maxn];
int fir[maxn], ec;
 
void add_edge(int u, int v, int w)
{
        edge[ec].to = v; edge[ec].cap = w;
        edge[ec].next = fir[u]; fir[u] = ec++;
        edge[ec].to = u; edge[ec].cap = 0;
        edge[ec].next = fir[v]; fir[v] = ec++;
}
 
void bfs(int s)
{
        memset(level, -1, sizeof(level));
        queue<int> que;
        que.push(s);
        level[s] = 0;
        while(!que.empty()) {
                int tmp = que.front(); que.pop();
                for(int i=fir[tmp]; i!=-1; i=edge[i].next) {
                        Edge &e = edge[i];
                        if(e.cap>0 && level[e.to]<0) {
                                level[e.to] = level[tmp]+1;
                                que.push(e.to);
                        }
                }
        }
}
 
int dfs(int v, int t, int f)
{
        if(v==t) return f;
        for(int &i=iter[v]; i!=-1; i=edge[i].next) {
                Edge &e = edge[i];
                if(e.cap>0 && level[e.to]>level[v]) {
                        int d = dfs(e.to, t, min(f, e.cap));
                        if(d>0) {
                                e.cap -= d;
                                edge[i^1].cap += d;
                                return d;
                        }
                }
        }
        return 0;
}
 
int max_flow(int s, int t)
{
        int res = 0, f;
        while(1) {
                bfs(s);
                if(level[t]<0) return res;
                memcpy(iter, fir, sizeof(fir));
                while((f = dfs(s, t, INF)) > 0)
                        res += f;
        }
}
 
强连通分量
 
void tarjan(int u)
{
    stack[++top] = u;
    dfn[u] = low[u] = ++Dindex;
    instack[u] = 1;
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(!dfn[v]) {
            tarjan(v);
            if(low[v]<low[u])
                low[u] = low[v];
        } else if(instack[v] && dfn[v]<low[u]) {
            low[u] = dfn[v];
        }
    }
    if(dfn[u]==low[u]) {
        int v;
        cnt++;
        do {
            v = stack[top--];
            instack[v] = 0;
            belong[v] = cnt;
        } while(u!=v);
    }
}
 
int find_scc()
{
    for(int i=1; i<=N; i++) {
        if(!dfn[i])
            tarjan(i);
    }
}
 
最小费用流
#define INF 0x3f3f3f3f
 
struct Edge {
        int to, cap, cost, rev;
        Edge(int a, int b, int c, int d):
                to(a), cap(b), cost(c), rev(d) {}
        Edge() {}
};
 
typedef pair<int, int> Pos;
const int maxv = 210;
 
int V;
vector<Edge> G[maxv];
int h[maxv], dis[maxv];
int prevv[maxv], preve[maxv];
 
void add_edge(int from, int to, int cap, int cost)
{
        G[from].push_back(Edge(to, cap, cost, G[to].size()));
        G[to].push_back(Edge(from, 0, -cost, G[from].size()-1));
}
 
int min_cost_flow(int s, int t, int f)
{
        int res = 0;
        memset(h, 0, sizeof(h));
        while(f > 0) {
                priority_queue<Pos, vector<Pos>, greater<Pos> > que;
                memset(dis, 0x3f, sizeof(dis));
                dis[s] = 0;
                que.push(Pos(0, s));
                while(!que.empty()) {
                        Pos tmp = que.top();
                        que.pop();
                        int v = tmp.second;
                        if(dis[v]<tmp.first)
                                continue;
                        for(int i=0; i<G[v].size(); i++) {
                                Edge &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;
                                        que.push(Pos(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);
                }
                f -= d;
                res += d*h[t];
                for(int v=t; v!=s; v=prevv[v]) {
                        Edge &e = G[prevv[v]][preve[v]];
                        e.cap -= d;
                        G[v][e.rev].cap += d;
                }
        }
        return res;
}
 
int min_cost_flow(int s, int t, int f)
{
        int res = 0;
        while(f > 0) {
                memset(dis, 0x3f, sizeof(dis));
                dis[s] = 0;
                bool update = true;
                while(update) {
                        update = false;
                        for(int v = 0; v<V; v++) {
                                if(dis[v]==INF) continue;
                                for(int i=0; i<G[v].size(); i++) {
                                        Edge &e = G[v][i];
                                        if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
                                                dis[e.to] = dis[v]+e.cost;
                                                prevv[e.to] = v;
                                                preve[e.to] = i;
                                                update = true;
                                        }
                                }
                        }
                }
                if(dis[t]==INF)
                        return -1;
                int d = f;
                for(int v=t; v!=s; v=prevv[v])
                        d = min(d, G[prevv[v]][preve[v]].cap);
                f -= d;
                res += d*dis[t];
                for(int v=t; v!=s; v=prevv[v]) {
                        Edge &e = G[prevv[v]][preve[v]];
                        e.cap -= d;
                        G[v][e.rev].cap += d;
                }
        }
        return res;
}
 
 
后缀数组
const int maxn = 20005;
 
int n, sa[maxn], lcp[maxn];
int sa_k, rank[maxn], tmp[maxn];
 
int cmp_sa(int a, int b)
{
        if(rank[a]!=rank[b])
                return rank[a] < rank[b];
        int ra = a+sa_k<=n ? rank[a+sa_k] : -1;
        int rb = b+sa_k<=n ? rank[b+sa_k] : -1;
        return ra < rb;
}
 
void cal_sa()
{
        for(int i=0; i<=n; i++) {
                rank[i] = str[i];
                sa[i] = i;
        }
        rank[n] = -1;
        for(sa_k=1; sa_k<=n; sa_k<<=1) {
                sort(sa, sa+n+1, cmp_sa);
                tmp[sa[0]] = 0;
                for(int i=1; i<=n; i++) {
                        tmp[sa[i]] = tmp[sa[i-1]] +
                        (cmp_sa(sa[i-1], sa[i]) ? 1 : 0);
                }
                for(int i=0; i<=n; i++)
                        rank[i] = tmp[i];
        }
}
 
// /str[sa[i]]和str[sa[i+1]]的公共前缀长度是lcp[i]
void cal_lcp()
{
        for(int i=0; i<=n; i++)
                rank[sa[i]] = i;
        int h = 0;
        for(int i=0; i<n; i++) {
                int j = sa[rank[i]-1];
                if(h>0) h--;
                for(; i+h<n && j+h<n; h++)
                        if(str[i+h]!=str[j+h])
                                break;
                lcp[rank[i]-1] = h;
        }
}
 
 
KMP算法
 
void getf(char *P, int *f)
{
        int pl = strlen(P);
        f[0] = f[1] = 0;
        for(int i=1; i<pl; i++) {
                int j = f[i];
                while(j && P[i]!=P[j]) j = f[j];
                f[i+1] = P[i]==P[j] ? j+1 : 0;
        }
}
 
int kmp(char *T, char *P)
{
        int tl = strlen(T);
        int pl = strlen(P), cnt = 0;
 
        getf(P, f);
        int j = 0;
        for(int i=0; i<tl; i++) {
                while(j && P[j]!=T[i]) j = f[j];
                if(P[j]==T[i]) j++;
                if(j==pl) cnt++;
        }
 
        return cnt;
}
 
 
几何
 
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Point {
    double x, y;
    Point(double x=0, double y=0):
        x(x), y(y) {}
};
 
typedef Point Vector;
const double eps = 1e-8;
const double PI = acos(-1.0);
int dcmp(double x) {
        if(fabs(x)<eps) return 0;
        else return x<0? -1 : 1;
}
 
bool operator == (const Point &a, const Point &b)
{
        return !dcmp(a.x-b.x) && !dcmp(a.y-b.y);
}
 
Point operator + (Point A, Point B)
{
        return Point(A.x+B.x, A.y+B.y);
}
 
Vector operator - (Point A, Point B)
{
        return Vector(A.x-B.x, A.y-B.y);
}
 
Vector operator * (Vector A, double n)
{
        return Vector(A.x*n, A.y*n);
}
 
double operator * (Vector A, Vector B)
{
        return A.x*B.x + A.y*B.y;
}
 
double operator ^ (Vector A, Vector B)
{
        return A.x*B.y - A.y*B.x;
}
 
bool operator < (const Point &A, const Point &B) {
        return A.x<B.x || (A.x==B.x && A.y<B.y);
}
 
double dist(Point A, Point B)
{
        return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
 
Point get_line_intersection(Point P, Vector v, Point Q, Vector w)
{
        Vector u = P-Q;
        double t = (w ^ u) / (v ^ w);
        return P + v*t;
}
 
int convex_hull(Point *p, int n, Point *ch)
{
        sort(p, p+n);
        int m = 0;
        for(int i=0; i<n; i++) {
                while(m>1 && ((ch[m-1]-ch[m-2]) ^ (p[i]-ch[m-2])) <= 0)
                        m--;
                ch[m++] = p[i];
        }
        int k = m;
        for(int i=n-2; i>=0; i--) {
                while(m>k && ((ch[m-1]-ch[m-2]) ^ (p[i]-ch[m-2])) <= 0)
                        m--;
                ch[m++] = p[i];
        }
        if(n>1) m--;
        return m;
}
 
背包
void zo_pack(int c, int w)
{
        for(int i = V; i >= c; i--) {
                f[i] = max(f[i], f[i - c] + w);
        }
}
 
void com_pack(int c, int w)
{
        for(int i = c; i <= V; i++) {
                f[i] = max(f[i], f[i - c] + w);
        }
}
 
void mul_pack(int c, int m, int w)
{
        if(c * m >= V) {
                com_pack(c, w);
                return ;
        }
        for(int k = 1; k < m; k *= 2) {
                zo_pack(c * k, w * k);
                m -= k;
        }
        zo_pack(c * m, w * m);
}
 
 
堆
typedef long long ll;
const int maxn = 3000000;
ll heap[maxn];
int qc;
 
void push(ll x)
{
        int p = ++qc;
        while(p/2 >= 1) {
                if(heap[p/2] <= x) break;
                heap[p] = heap[p/2];
                p = p/2;
        }
        heap[p] = x;
}
 
void pop()
{
        ll x = heap[qc--];
        int p = 1;
        while(p*2 <= qc) {
                int l = p*2;
                if(l+1<=qc && heap[l]>heap[l+1])
                        l = l+1;
                if(x <= heap[l]) break;
                heap[p] = heap[l];
                p = l;
        }
        heap[p] = x;
}

标签: none

仅有一条评论

  1. Nicely put. Thanks a lot!

添加新评论