ACM模板手写,不定更新
在此整理了一些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;
}
Nicely put. Thanks a lot!