Eternity

Until The End

代码风格规范 & 模板汇总

发表于 更新于 分类于
本文字数： 33k 阅读时长 ≈ 30 分钟

$\text{_Eternal_}$ 不成文的代码风格。

代码风格

考场缺省源

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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    
    return 0;
}
/*

*/

宏定义

1
2
3
4
#define re register		//一般不使用，除非卡常
typedef long long ll;		//此处使用小写。
//#define int long long 	//必要时使用
//#define int __int128		//很必要时使用

函数，语法规范

首先申明：

  • 不能：在任何情况下都不能使用。
  • 可以：在一定条件下使用。
  • 必须：任何情况都要使用。
  • 一般：在大多数情况下。
  1. 非递归函数必须加上 inline ，递归函数不能加上 inline 。
  2. 涉及数组大小的常量必须加上 const 。
  3. 函数命名一般使用驼峰式命名。
  4. 全局变量一般使用大写，局部变量一般使用小写。
  5. 一般压行。
  6. 大括号必须单独一行。
  7. 不能打空格。
  8. 不能打 using namespace std; ，需要使用是调用 std:: 。

常量定义

1
const int MAXN,MAXM,MAXK,MAXV,MAXE,MAXNUM...;

全大写单词 MAX 加上题目定义的字符（可以不止一个）。

1
2
3
4
5
const int INF=0x3f3f3f3f;
const int INF=0x7f7f7f7f;
const ll INF=1145141919810;
const ll INF=1e18;
const int Mod=1e9+7;

INF 一般为以上四种，Mod 视题目而定。

1
2
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};

用于在二维网格图中进行扩展，具体扩展方式视题目而定。dx,dy 必须将 [0] 空出。

总参数定义

1
2
3
4
5
6
7
8
9
10
11
12
13
int N;					//数列长度，图/树的点数等
int M;					//图的边数，要求个数等
int Q;					//询问次数
int Test;				//数据个数
int K;					//操作个数，要求个数等
int ans,res,ret;			//全局最优答案，局部最优答案，最小费用（费用流专属）
int Cnt,Tot,Total,Idx;			//计数类参数
int Rt,Root;				//树根
int V,W,T;				//价值总和，总金额（背包等问题专属）
int Sum;				//总和
int i,j,k,l,p,q,t;			//循环字节（依次，可变换）
int len,l,r,k;				//循环字节（区间Dp专属）
int Len,Length;				//数列长度等（一般是离散化之后）

数列定义

1
2
3
4
5
6
int Val[MAXN],Num[MAXN],a[MAXN],b[MAXN];
int main()
{
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]);
}

一般情况下，下标从 $1$ 开始。

字符串定义

1
2
3
4
5
6
7
char Str[MAXN],S[MAXN];
std::string Str;
int main()
{
    scanf("%s",Str+1);
    N=strlen(Str+1);	//N=Str.size()+1;
}

一般情况下，下标从 $1$ 开始。

图定义

1
2
3
4
G Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int,int,int);		//链式前向星存图
std::vector<int>Edges[MAXN];			//vector存图

网络定义

1
2
3
Net Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int,int,int);		//链式前向星存储网络

树定义

1
2
3
Tre Edge[MAXN<<1];
int Head[MAXN],Total,Rt=1;
inline void addEdge(int,int,int);		//链式前向星存储树型结构

动态规划定义

1
2
int f[MAXN][MAXM],g[MAXK][MAXN];
int Dp[MAXN][MAXK];			//最终答案数组

数据结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Tre[MAXN];				//树状数组
#define ls p<<1
#define rs p<<1|1
ST Tree[MAXN<<2];			//线段树，主席树
#define ls(p) Tr[p].chi[0]
#define rs(p) Tr[p].chi[1]
B_T Tr[MAXN]				//Splay类可旋平衡树
int Fa[MAXN],Siz[MAXN],Dep[MAXN],Son[MAXN];
int Top[MAXN],Dfn[MAXN],Bck[MAXN],Cnt;
					//树链剖分
					//父结点，子树大小，结点深度，重儿子编号
					//链顶，dfs序，dfs序的反定义，dfs序计数
int Bel[MAXN],Lst[MAXB],Nxt[MAXB],Uni,All;
					//分块
					//块号，块的左端点，右端点，块长，块数
int St[MAXN][MAXS]; 			//st表，倍增
int Tri[MAXN][MAXS]			//Trie树
int Fail[MAXN],Ch[MAXN][MAXS];		//AC自动机

函数定义

1
2
3
4
5
6
7
8
9
10
11
void dfs();					//void Dfs();
inline void bfs();				//inline void Bfs();
						//搜索
inline void Spfa();
inline void Dijkstra();
inline void Floyd();				//最短路算法
inline void init();				//初始化
inline void sieve();				//线性筛
inline void solve();
inline void calc();
inline void work();				//计算类函数

总之，有名字的算法一般以其名字作为函数名，否则使用一个通俗且显而易见的名字。

具体函数可见模板。

模板汇总

FastIO

$\text{Fast In/Out}$ ，快读快输模板，我比较喜欢第一种，第二种适用于交互题，不会用。

Version Ⅰ

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
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}

Version Ⅱ

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
namespace FastIO
{
    const int L=(1<<20)+100;
    char buf[L],out[L],*S,*E;
    int l=0;
    #define gh() (S==E?E=(S=buf)+fread(buf,1,L,stdin),(S==E?EOF:*S++):*S++)
    void flus()
    {
        fwrite(out,1,l,stdout),l=0;
    }
    void check()
    {
        if(l>=L-100) flus();
    }
    void putc(char x)
    {
        out[l++]=x,check();
    }
    void read(char *s)
    {
        char ch=gh();
        while(ch<33||ch>126) ch=gh();
        for(;ch>=33&&ch<=126;ch=gh()) *s++=ch;
        *s='\0';
    }
    void write(char *s)
    {
        while(*s!='\0') putc(*s++);
    }
    void write(const char *s)
    {
        while(*s!='\0') putc(*s++);
    } //这是为了可以直接""构造字符串输出
    template<typename T>
    void read(T &x)
    {
        x=0;
        char ch=gh(),t=0;
        while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
        if(t) x=-x;
    }
    template<typename T>
    void write(T x)
    {
        if(x<0) putc('-'),x=-x;
        if(x>9) write(x/10);
        out[l++]=x%10+48,check();
    }
    template<typename T,typename ...Args>
    void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename ...Args>
    void read(char *x,Args ...args)
    {
        read(x),read(args...);
    }
    template<typename T,typename ...Args>
    void write(T x,Args ...args)
    {
        write(x),write(args...);
    }
    #undef gh
}
using FastIO::flus;
using FastIO::read;
using FastIO::write;

数据结构

线段树

可扩展性强，模板没有太多可借鉴性，而且还比较好背。

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
#define ls p<<1
#define rs p<<1|1
struct ST
{
    int l,r,val,tag;
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    //Code
}
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        //Code;
        Tree[p].tag=INIT:
    }
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r;
    if(l==r)
    {
        //Code;
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushUp(p);
}
void modify(int p,int l,int r,int k)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        //Code;
        return ;
    }
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modify(ls,l,r,k);
    if(mid<r) modify(rs,l,r,k);
    pushUp(p);
}
int query(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return /*Code*/;
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1,res=INIT;
    if(l<=mid) res=calc(res,query(ls,l,r));
    if(mid<r) res=calc(res,query(rs,l,r));
    return res;
}

树状数组

可扩展性没有线段树强，但常数较小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Tre[MAXN];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int k)
{
    for(;x<=N;x+=lowbit(x)) Tre[x]+=k;
}
inline void query(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=Tre[x];
    return res;
}

主席树 / 可持久化线段树

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
int Idx,Rt[MAXN];
struct PST
{
    int lc,rc,val;
}Tree[MAXN*100];
inline void pushUp(int x)
{
    Tree[x].val+=Tree[Tree[x].lc].val+Tree[Tree[x].rc].val;
}
void modify(int &x,int l,int r,int d)
{
    Tree[++Idx]=Tree[x];x=Idx;
    if(l==r)
    {
        ++Tree[x].val;
        return ;
    }
    int mid=(l+r)>>1;
    if(d<=mid) modify(Tree[x].lc,l,mid,d);
    else modify(Tree[x].rc,mid+1,r,d);
    pushUp(x);
}
int query(int x1,int x2,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int ls=Tree[Tree[x2].lc].val-Tree[Tree[x1].lc].val;
    if(k<=ls) return query(Tree[x1].lc,Tree[x2].lc,l,mid,k);
    else return query(Tree[x1].rc,Tree[x2].rc,mid+1,r,k-ls);
}

扫描线（矩阵面积并）

先搁着，需要重新学习一下。

左偏树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Fa[MAXN],Le[MAXN],Ri[MAXN];
bool Del[MAXN];
inline bool Cmp(int x,int y)
{
    if(Val[x]==Val[y]) return x<y;
    return Val[x]<Val[y];
}
int getFa(int x)
{
    return Fa[x]==x?x:Fa[x]=getFa(Fa[x]);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(Cmp(y,x)) std::swap(x,y);
    Ri[x]=merge(Ri[x],y);
    if(Dist[Ri[x]]>Dist[Le[x]]) std::swap(Le[x],Ri[x]);
    Dist[x]=Dist[Ri[x]]+1;
    return x;
}

李超线段树

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
struct Line
{
    int l,r,tag;
    double k,b;
}Tree[MAXN<<2];
inline double calc(Line a,int x);	//求线段a横坐标为x时的纵坐标
inline int cross(Line a,Line b);	//求线段交点
void modify(int p,int l,int r,Line k)
{
    if(k.l<=l&&r<=k.r)
    {
        if(!Tree[p].tag) Tree[p]=k,Tree[p].tag=1;
        else if(calc(k,l)-calc(Tree[p],l)>eps&&calc(k,r)-calc(Tree[p],r)>eps) Tree[p]=k;
        else if(calc(k,l)-calc(Tree[p],l)>eps||calc(k,r)-calc(Tree[p],r)>eps)
        {
            int mid=(l+r)>>1;
            if(calc(k,mid)-calc(Tree[p],mid)>eps) std::swap(k,Tree[p]);
            if(mid-cross(k,Tree[p])>eps) modify(ls,l,mid,k);
            else modify(rs,mid+1,r,k);
        }
    }
    else
    {
        int mid=(l+r)>>1;
        if(k.l<=mid) modify(ls,l,mid,k);
        if(mid<k.r) modify(rs,mid+1,r,k);
    }
}
double query(int p,int l,int r,int k)
{
    if(l==r) return calc(Tree[p],k);
    else
    {
        int mid=(l+r)>>1;
        double ans=calc(Tree[p],x);
        if(k<=mid) return std::max(ans,query(ls,l,mid,k));
        else return std::max(ans,query(rs,mid+1,r,k));
    }
}

Splay系平衡树

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
struct Splay
{
    int chi[2],fa;
    int num,id,dat;
}Tree[MAXN];
int Rt;
inline void pushUp(int x)
{
    Tree[x].id=Tree[Tree[x].chi[0]].id+Tree[Tree[x].chi[1]].id+Tree[x].num;
}
inline void rotate(int x)
{
    int y=Tree[x].fa,z=Tree[y].fa;
    int k=Tree[y].chi[1]==x;
    Tree[z].chi[Tree[z].chi[1]==y]=x;
    Tree[x].fa=z;
    Tree[y].chi[k]=Tree[x].chi[k^1];
    Tree[Tree[x].chi[k^1]].fa=y;
    Tree[x].chi[k^1]=y;
    Tree[y].fa=x;
    pushUp(y);
    pushUp(x);
}
inline void Splay(int x,int k)
{
    while(Tree[x].fa!=k)
    {
        int y=Tree[x].fa,z=Tree[y].fa;
        if(z!=k)
            if((Tree[y].chi[1]==x)^(Tree[z].chi[1]==y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) Rt=x;
}

FHQ-Treap

个人比较喜欢写的一种平衡树，也比较好写，就把一些常用的函数也贴上了。

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
struct B_T
{
    int Idx=0,Rt=0,x,y,z;
    struct Fhq_Treap
    {
        int siz,val,rd,chi[2];
    }Tree[MAXN];
    #define ls(p) Tree[p].chi[0]
    #define rs(p) Tree[p].chi[1]
    inline int newNode(int v)
    {
        Tree[++Idx]={1,v,rand()};
        return Idx;
    }
    inline void update(int p)
    {
        Tree[p].siz=Tree[ls(p)].siz+Tree[rs(p)].siz+1;
    }
    inline void split(int p,int k,int &u,int &v)
    {
        if(!p) u=v=0;
        else
        {
            if(Tree[p].val<=k) u=p,split(rs(p),k,rs(p),v);
            else v=p,split(ls(p),k,u,ls(p));
            update(p);
        }
        return ;
    }
    inline int merge(int u,int v)
    {
        if(!u||!v) return u+v;
        if(Tree[u].rd<Tree[v].rd)
        {
            rs(u)=merge(rs(u),v);
            update(u);
            return u;
        }
        else
        {
            ls(v)=merge(u,ls(v));
            update(v);
            return v;
        }
    }
    inline void insert(int v)
    {
        x=y=0;
        split(Rt,v,x,y);
        Rt=merge(merge(x,newNode(v)),y);
    }
    inline void del(int v)
    {
        x=y=z=0;
        split(Rt,v,x,z),split(x,v-1,x,y);
        y=merge(ls(y),rs(y));
        Rt=merge(merge(x,y),z);
    }
    inline int rank(int v)
    {
        x=y=0;
        split(Rt,v-1,x,y);
        int res=Tree[x].siz+1;
        Rt=merge(x,y);
        return res;
    }
    inline int kth(int p,int k)
    {
        while(1)
        {
            if(k<=Tree[ls(p)].siz) p=ls(p);
            else if(k==Tree[ls(p)].siz+1) return p;
            else k-=Tree[ls(p)].siz+1,p=rs(p);
        }
    }
    inline int pre(int v)
    {
        x=y=0;
        split(Rt,v-1,x,y);
        int res=Tree[kth(x,Tree[x].siz)].val;
        Rt=merge(x,y);
        return res;
    }
    inline int nxt(int v)
    {
        x=y=0;
        split(Rt,v,x,y);
        int res=Tree[kth(y,1)].val;
        Rt=merge(x,y);
        return res;
    }
}Tree;

莫队

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
struct Query
{
    int l,r,id;
    bool operator<(const Query &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        return (l?Uni)&1?r<x.r:r>x.r;
    }
}Q[MAXN];
inline void add(int pos)
{
    //Code
}
inline void del(int pos)
{
    //Code
}
inline void Solve()
{
    std::sort(Q+1,Q+1+M);
    for(int i=1,l=1,r=0;i<=M;++i)
    {
        auto q=Q[i];
        if(q.l==q.r)
        {
            ans[0][q.id]=0,ans[1][q.id]=1;
            continue;
        }
        while(l>q.l) add(Val[--l]);
        while(r<q.r) add(Val[++r]);
        while(l<q.l) del(Val[l++]);
        while(r>q.r) del(Val[r--]);
        ans=/*Code*/;
    }
    return ;
}

带修莫队

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
struct Que
{
    int id,l,r,t;
    bool operator<(const Que &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        if(r/Uni!=x.r/Uni) return r<x.r;
        return t<x.t;
    }
}Q[MAXN];
struct Modify
{
    int p,c;
}Ch[MAXN];
int res;
inline void add(int x)
{
    //Code;
}
inline void del(int x)
{
    //Code;
}
inline void Solve()
{
    std::sort(Q+1,Q+1+Mq);
    for(int i=1,l=2,r=1,t=0;i<=Mq;++i)
    {
        auto q=Q[i];
        while(l>q.l) add(Val[--l]);
        while(r<q.r) add(Val[++r]);
        while(l<q.l) del(Val[l++]);
        while(r>q.r) del(Val[r--]);
        while(t<q.t)
        {
            ++t;
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                del(Val[Ch[t].p]);
                add(Ch[t].c);
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
        }
        while(t>q.t)
        {
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                del(Val[Ch[t].p]);
                add(Ch[t].c);
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
            --t;
        }
        ans[q.id]=res;
    }
}
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
struct Tre
{
    int chi[2],fa,val;
    int sum,rev;
}Tr[MAXN];
int Stk[MAXN];


inline void pushRev(int p)
{
    std::swap(Tr[p].chi[0],Tr[p].chi[1]);
    Tr[p].rev^=1;
}
inline void pushUp(int p)
{
    Tr[p].sum=Tr[ls(p)].sum^Tr[rs(p)].sum^Tr[p].val;
}
inline void pushDown(int p)
{
    if(Tr[p].rev)
    {
        pushRev(ls(p)),pushRev(rs(p));
        Tr[p].rev=0;
    }
}
inline bool isRoot(int p)
{
    return ls(Tr[p].fa)!=p&&rs(Tr[p].fa)!=p;
}
inline void rotate(int x)
{
    int y=Tr[x].fa,z=Tr[y].fa;
    int k=rs(y)==x;
    if(!isRoot(y)) Tr[z].chi[rs(z)==y]=x;
    Tr[x].fa=z;
    Tr[y].chi[k]=Tr[x].chi[k^1],Tr[Tr[x].chi[k^1]].fa=y;
    Tr[x].chi[k^1]=y,Tr[y].fa=x;
    pushUp(y),pushUp(x);
}
inline void Splay(int x)
{
    int r=x,Top=0;
    Stk[++Top]=r;
    while(!isRoot(r)) Stk[++Top]=r=Tr[r].fa;
    while(Top) pushDown(Stk[Top--]);
    while(!isRoot(x))
    {
        int y=Tr[x].fa,z=Tr[y].fa;
        if(!isRoot(y))
            if((rs(y)==x)^(rs(z)==y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}
//建立从根到x的路径，并将x变成Splay的根结点
inline void access(int x)
{
    int z=x;
    for(int y=0;x;y=x,x=Tr[x].fa)
    {
        Splay(x);
        rs(x)=y,pushUp(x);
    }
    Splay(z);
}
//将x变成原树的根结点
inline void makeRoot(int x)
{
    access(x);
    pushRev(x);
}
//找到当前x所在原树的根结点，并把原树的根结点旋转到Splay的根结点
inline int findRoot(int x)
{
    access(x);
    while(ls(x)) pushDown(x),x=ls(x);
    Splay(x);
    return x;
}
//在x到y中的路径中建立一个Splay，其根结点为y
inline void split(int x,int y)
{
    makeRoot(x);
    access(y);
}
//如果x,y不连通，加入边(x,y)
inline void link(int x,int y)
{
    makeRoot(x);
    if(findRoot(y)!=x) Tr[x].fa=y;
}
//如果x,y连通，删除边(x,y)
inline void cut(int x,int y)
{
    makeRoot(x);
    if(findRoot(y)==x&&Tr[y].fa==x&&!ls(y))
    {
        rs(x)=Tr[y].fa=0; 
        pushUp(x);
    }
}
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
int N,M,Idx,Top;
int Le[MAXN],Ri[MAXN],Up[MAXN],Do[MAXN];
//十字链表的左右上下指针
int Cnt[MAXN],Row[MAXN],Col[MAXN];
//链表长度，行列信息
int ans[MAXN];
inline void init()
{
    for(re int i=0;i<=M;++i)
    {
        Le[i]=i-1,Ri[i]=i+1;
        Up[i]=Do[i]=i;
    }
    Le[0]=M,Ri[M]=0;
    Idx=M+1;
}
inline void add(int &he,int &ta,int x,int y)
{
    Row[Idx]=x,Col[Idx]=y,++Cnt[y];
    Up[Idx]=y,Do[Idx]=Do[y],Up[Do[y]]=Idx,Do[y]=Idx;
    Ri[he]=Le[ta]=Idx,Ri[Idx]=ta,Le[Idx]=he;
    ta=Idx++;
}
inline void remove(int p)	//删除
{
    Ri[Le[p]]=Ri[p],Le[Ri[p]]=Le[p];
    for(re int i=Do[p];i!=p;i=Do[i])
        for(re int j=Ri[i];j!=i;j=Ri[j])
        {
            --Cnt[Col[j]];
            Up[Do[j]]=Up[j],Do[Up[j]]=Do[j];
        }
}
inline void recover(int p)	//恢复
{
    for(re int i=Up[p];i!=p;i=Up[i])
        for(re int j=Le[i];j!=i;j=Le[j])
        {
            Up[Do[j]]=j,Do[Up[j]]=j;
            ++Cnt[Col[j]];
        }
    Ri[Le[p]]=p,Le[Ri[p]]=p;
}
bool dfs()
{
    if(!Ri[0]) return 1;
    int p=Ri[0];
    for(re int i=Ri[0];i;i=Ri[i])
        	if(Cnt[i]<Cnt[p]) p=i;
    remove(p);
    for(re int i=Do[p];i!=p;i=Do[i])
    {
        ans[++Top]=Row[i];
        for(re int j=Ri[i];j!=i;j=Ri[j]) remove(Col[j]);
        if(dfs()) return 1;
        for(re int j=Le[i];j!=i;j=Le[j]) recover(Col[j]);
        --Top;
    }
    recover(p);
    return 0;
}

字符串系算法

Trie字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void insert(char *s)
{
    int u=0,len=strlen(s+1);	//根节点
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][s[i]]) Tre[u][s[i]]=++Cnt;	//建立新节点
        u=Tre[u][s[i]];			//往后跳
    }
}
inline bool query(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][s[i]]) return 0;		//不存在
        u=Tre[u][s[i]];
	}
    return 1;		//存在
}

KMP字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=2,j=0;i<=N;++i)
{
    while(j&&strb[i]!=strb[j+1]) j=Fail[j];
    if(strb[i]==strb[j+1]) ++j;
    Fail[i]=j;
}
for(int i=1,j=0;i<=M;++i)
{
    while(j&&stra[i]!=strb[j+1]) j=Fail[j];
    if(stra[i]==strb[j+1]) ++j;
    if(j==N) puts("Connect!");
}

AC自动机

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
void addString(char *s)
{
    int u=0,len=strlen(s+1);	//约定0为空根节点，字符串从1开始
    for(int i=1,c;i<=len;++i)
    {
        if(!ch[u][(c=s[i]-'a')]) ch[u][c]=++cnt;
        u=ch[u][c];
	}
    ++End[u];		//记录尾结点为u的字串的个数
}
inline void compare()
{
    queue<int>Q;
    for(int i=0;i<26;++i) if(ch[0][i]) Q.push(ch[0][i]);
    		//放入根节点
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=0;i<26;++i)		//遍历u的儿子
        {
            if(!ch[u][i]) ch[u][i]=ch[Fail[u]][i];
            						//没有该边，直接相连
            else
            {
                Q.push(ch[u][i]);
                Fail[ch[u][i]]=ch[Fail[u]][i];
                					//失配
            }
        }
    }
}
inline void calc(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;++i)
    {
        int c=s[i]-'a';
        u=ch[u][c];
        for(int j=u;j&&End[j]!=-1;j=Fail[j])
            ans+=End[j],End[j]=-1;		//避免重复
    }
    return ;
}

后缀自动机

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
namespace SAM
{
    struct State
    {
        int len,link,next[27];
    }Tre[MAXN<<1];
    struct Path
    {
        int next,to;
    }Edge[MAXN<<1];
    int Total,Head[MAXN];
    inline void addEdge(int u,int v)
    {
        Edge[++Total]=(Path){Head[u],v};Head[u]=Total;
    }
    int Last,Size=0,Endpos[MAXN],T[MAXN],A[MAXN];
    ll ans=0;
    inline void init()
    {
        Tre[1].len=0,Tre[1].link=0;
        Last=1,Size=1;
        memset(Endpos,0,sizeof(Endpos));
        memset(T,0,sizeof(T));
        memset(A,0,sizeof(A));
    }
    inline void Extend(char c)
    {
        int cur=++Size;
        Tre[cur].len=Tre[Last].len+1;
        int p=Last;
        Endpos[cur]=1;
        while(p&&!Tre[p].next[c-'a'])
        {
            Tre[p].next[c-'a']=cur;
            p=Tre[p].link;
        }
        if(!p) Tre[cur].link=1;
        else
        {
            int q=Tre[p].next[c-'a'];
            if(Tre[p].len+1==Tre[q].len) Tre[cur].link=q;
            else
            {
                int clone=++Size;
                Tre[clone]=Tre[q];
                Tre[clone].len=Tre[p].len+1;
                while(p&&Tre[p].next[c-'a']==q)
                {
                    Tre[p].next[c-'a']=clone;
                    p=Tre[p].link;
                }
                Tre[q].link=Tre[cur].link=clone;
            }
        }
        Last=cur;
    }
    void dfs(int x)
    {
        for(int e=Head[x];e;e=Edge[e].next)
        {
            dfs(Edge[e].to);
            Endpos[x]+=Endpos[Edge[e].to];
        }
        ll res=Endpos[x]*Tre[x].len;
        if(Endpos[x]!=1) checkMax(ans,res);
    }
    inline void calc()
    {
        for(int i=2;i<=Size;++i) addEdge(Tre[i].link,i);
        dfs(1);
        printf("%lld",ans);
    }
};

ExKmp/Z-func

不长考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void Z_Func(char *s,int n)
{
    Z[0]=n;
    int now=0;
    while(now+1<n&&s[now]==s[now+1]) ++now;
    Z[1]=now;
    int p=1;
    for(int i=2;i<n;++i)
    {
        if(i+Z[i-p]<p+Z[p]) Z[i]=Z[i-p];
        else
        {
            now=p+Z[p]-i;
            now=std::max(now,0);
            while(now+i<n&&s[now]==s[now+i]) ++now;
            Z[i]=now;
            p=i;
        }
    }
}

Manacher

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
#include<bits/stdc++.h>
const int MAXN=1.1e7+10;
char S[MAXN],Str[MAXN<<1];
int N,Cnt,P[MAXN<<1],ans;
int main()
{
    scanf("%s",S+1);
    N=strlen(S+1);
    Str[++Cnt]='~',Str[++Cnt]='#';
    for(int i=1;i<=N;++i) Str[++Cnt]=S[i],Str[++Cnt]='#';
    Str[++Cnt]='!';
    for(int i=2,mr=0,mid=0;i<Cnt;++i)
    {
        if(i<=mr) P[i]=std::min(P[(mid<<1)-i],mr-i+1);
        else P[i]=1;
        while(Str[i-P[i]]==Str[i+P[i]]) ++P[i];
        if(i+P[i]>mr) mr=i+P[i]-1,mid=i;
        ans=std::max(ans,P[i]);
    }
    printf("%d",ans-1);
    return 0;
}
/*
aaa
*/

数学论系

快速幂

1
2
3
4
5
6
7
8
9
10
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;b>>=1;
    }
    return res;
}

线性筛

筛了质数，欧拉函数和莫比乌斯函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Tot;
int pri[MAXN],phi[MAXN],mu[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
    mu[1]=phi[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!is[i]) pri[++Tot]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
        {
            is[i*pri[j]]=0;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }    
            mu[i*pri[j]]=-mu[i];
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}

Exgcd

1
2
3
4
5
6
7
8
9
10
void Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return ;
    }
    Exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-a/b*y;
}

CRT

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
struct Node
{
    LL type,mod;
}Num[MAXN];
LL M[MAXN],Mul=1,Mi[MAXN],X;
inline void Exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return ;
    }
    Exgcd(b,a%b,x,y);
    LL z=x;x=y;y=z-y*(a/b);
}
int main()
{
    // freopen("china.in","r",stdin);
    // freopen("china.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i)
    {
        read(Num[i].type),read(Num[i].mod);
        Mul*=Num[i].type;
    }
    for(int t=1;t<=N;++t)
    {
        Mi[t]=Mul/Num[t].type;
        LL x=0,y=0;
        Exgcd(Mi[t],Num[t].type,x,y);
        X+=Num[t].mod*Mi[t]*(x<0?x+Num[t].type:x);
    }
    printf("%lld",X%Mul);
    return 0;
}

EXCRT

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
ll N,px[MAXN],bx[MAXN];
inline ll qMul(ll a,ll b,ll p)
{
    ll res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;b>>=1;
    }
    return res;
}
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=qMul(res,a,p);
        a=qMul(a,a,p);b>>=1;
    }
    return res;
}
ll Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll gcd=Exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-a/b*x;
    return gcd;
}
ll Excrt()
{
    ll x,y,k;
    ll M=bx[1],ans=px[1];
    for(int i=2;i<=N;++i)
    {
        ll a=M,b=bx[i],c=(px[i]-ans%b+b)%b;
        ll Gcd=Exgcd(a,b,x,y),Bg=b/Gcd;
        if(c%Gcd!=0) return -1;
        x=qMul(x,c/Gcd,Bg);
        ans+=x*M;M*=Bg;ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
int main()
{
    // freopen("excrt.in","r",stdin);
    // freopen("excrt.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(bx[i],px[i]);
    write(Excrt());
    return 0;
}
/*
3
11 6
25 9
33 17
*/

BSGS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll Bsgs(ll a,ll b,ll p)
{
    std::map<ll,ll>Hash;Hash.clear();
    b%=p;
    ll t=std::sqrt(p)+1;
    for(ll i=0;i<t;++i) Hash[b*qPow(a,i,p)%p]=i;
    a=qPow(a,t,p);
    if(!a) return b==0?1:-1;
    for(ll i=1;i<=t;++i)
    {
        ll res=qPow(a,i,p);
        int j=Hash.find(res)==Hash.end()?-1:Hash[res];
        if(j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;
}

EXBSGS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline ll ExBsgs(ll a,ll b,ll p)
{
    if(b==1||p==1) return 0;
    ll d=Gcd(a,p),k=0,Na=1;
    while(d>1)
    {
        if(b%d!=0) return -1;
        ++k;b/=d;p/=d;Na=Na*(a/d)%p;
        if(Na==b) return k;
        d=Gcd(a,p);
    }
    ll f=Bsgs(a,b*Inv(Na,p)%p,p);
    if(f==-1) return -1;
    return f+k;
}

高斯消元

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
double Matrix[MAXN][MAXN];
inline bool gauss()
{
    for(int i=1;i<=N;++i)
    {
        int t=i;
        for(int j=i+1;j<=N;++j)
        {
            if(fabs(Matrix[j][i])>fabs(Matrix[t][i])) t=j;
        }
        for(int j=1;j<=N+1;++j) std::swap(Matrix[t][j],Matrix[i][j]);
        if(!Matrix[i][i]) return 0;
        for(int j=1;j<=N;++j)
        {
            if(j!=i)
            {
                double temp=Matrix[j][i]/Matrix[i][i];
                for(int k=i+1;k<=N+1;++k)
                {
                    Matrix[j][k]-=Matrix[i][k]*temp;
                }
            }
        }
    }
    for(int i=N;i>0;--i)
    {
        for(int j=i+1;j<=N;++j)
        {
            Matrix[i][N]-=Matrix[i][j]*Matrix[j][N];
        }
    }
    return 1;
}

数论分块

1
2
3
4
5
for(int l=1,r=0;l<=N;l=r+1)
{
    r=N/(N/l);
    //Code
}

拉格朗日插值

1
2
3
4
5
6
7
8
9
10
read(N,K);
for(int i=1;i<=N;++i) read(Dx[i],Dy[i]);
for(int i=1;i<=N;++i)
{
    s1=Dy[i]%Mod,s2=1;
    for(int j=1;j<=N;++j)
        if(i!=j) s1=s1*(K-Dx[j])%Mod,s2=s2*(Dx[i]-Dx[j])%Mod;
    ans+=s1*inv(s2)%Mod;
}
write((ans%Mod+Mod)%Mod);	//以防负数

快速傅里叶变换

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
struct Complex
{
    double x,y;
    Complex operator+(const Complex& t) const
    {
        return {x+t.x,y+t.y};
    }
    Complex operator-(const Complex& t) const
    {
        return {x-t.x,y-t.y};
    }
    Complex operator*(const Complex& t) const
    {
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[MAXN],b[MAXN];
int Rev[MAXN],Bit,Tot;
inline void Fft(Complex a[],int inv)
{
    for(int i=0;i<Tot;++i)
        if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
    for(int mid=1;mid<Tot;mid<<=1)
    {
        auto w_1=Complex({std::cos(Pi/mid),inv*std::sin(Pi/mid)});
        for(int i=0;i<Tot;i+=mid*2)
        {
            auto w_k=Complex({1,0});
            for(int j=0;j<mid;++j,w_k=w_k*w_1)
            {
                auto x=a[i+j],y=w_k*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
}

图论

链式前向星

1
2
3
4
5
6
7
8
9
10
struct G
{
    int next,to,val;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}

树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Fa[MAXN],Son[MAXN],Dep[MAXN],Size[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Dep[x]=Dep[last]+1,Size[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Size[x]+=Size[v];
        if(!Son[x]||Size[v]>Size[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],Dfn[MAXN],Cnt;
void dfsChain(int x,int topf)
{
    Dfn[x]=++Cnt,Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}

网络流

最大流最小割

只用 $\text{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
const int INF=0x3f3f3f3f;
int N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXM<<2];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    std::queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1,Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        v=Edge[e].to,Cur[x]=e;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}

费用流

同样只贴有用的 $\text{SSP-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
int N,M,S,T;
struct Net
{
    int next,to,val,cost;
    Net(int n=0,int t=0,int v=0,int c=0):
        next(n),to(t),val(v),cost(c){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w,int c)
{
    Edge[++Total]=Net(Head[u],v,w,c);Head[u]=Total;
    Edge[++Total]=Net(Head[v],u,0,-c);Head[v]=Total;
}
int Dist[MAXN],ret;
bool Vis[MAXN];
inline bool Spfa(int s,int t)
{
    memset(Dist,0x3f,sizeof(Dist));
    memcpy(Cur,Head,sizeof(Head));
    queue<int>Q;
    Q.push(s),Dist[s]=0,Vis[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        Vis[u]=0;
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Edge[e].val&&Dist[v]>Dist[u]+Edge[e].cost)
            {
                Dist[v]=Dist[u]+Edge[e].cost;
                if(!Vis[v]) Q.push(v),Vis[v]=1;
            }
        }
    }
    return Dist[t]!=INF;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    Vis[x]=1;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(!Vis[v]&&Edge[e].val&&Dist[v]==Dist[x]+Edge[e].cost)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(k)
            {
                ret+=k*Edge[e].cost;
                Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
            }
        }
    }
    Vis[x]=0;
    return flow;
}
inline int Dinic()
{
    int res=0,flow;
    while(Spfa(S,T)) while(flow=Dfs(S,INF)) res+=flow;
    return res;
}

有源汇上下界最大流

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=501;
const int MAXM=2e4+1;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,S,T,Sv,Tv;
struct Graph
{
    int next,to,val;
    Graph(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int A[MAXN],Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[Sv]=0,Cur[Sv]=Head[Sv];
    queue<int>Q;
    Q.push(Sv);
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int e=Head[x];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[x]+1;
                Cur[v]=Head[v];
                if(v==Tv) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==Tv) return inf;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(Sv,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("maxflow.in","r",stdin);
    // freopen("maxflow.out","w",stdout);
    read(N,M,S,T);
    Sv=0,Tv=N+1;
    for(int i=1,u,v,w,c;i<=M;++i)
    {
        read(u,v,w,c);
        addEdge(u,v,c-w);
        A[u]-=w,A[v]+=w;
    }
    int Tot=0;
    for(int i=1;i<=N;++i)
        if(A[i]>0) addEdge(Sv,i,A[i]),Tot+=A[i];
        else if(A[i]<0) addEdge(i,Tv,-A[i]);
    addEdge(T,S,INF);
    if(Dinic()<Tot) puts("please go home to sleep");
    else
    {
        int res=Edge[Total].val;
        Sv=S,Tv=T;
        Edge[Total].val=Edge[Total-1].val=0;
        printf("%d\n",res+Dinic());
    }
    return 0;
}
/*
10 15 9 10
9 1 17 18
9 2 12 13
9 3 11 12
1 5 3 4
1 6 6 7
1 7 7 8
2 5 9 10
2 6 2 3
2 7 0 1
3 5 3 4
3 6 1 2
3 7 6 7
5 10 16 17
6 10 10 11
7 10 14 15
*/

有源汇上下界最小流

只贴和最大流不同的地方。

1
2
3
4
5
6
7
else
   {
       int res=Edge[Total].val;
       vS=T,vT=S;						//不同点1
       Edge[Total].val=Edge[Total-1].val=0;
       printf("%d",res-Dinic());		//不同点2
   }

其他技巧

模拟退火

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
inline int randSeed()
{
    //Code
}
inline int calc()
{
    //Code
}
inline void simulate()
{
    for(double T=T0;T>Te;T*=Tk)
    {
        int x=randSeed(),y=randSeed();
        if(x==y) continue;
        /*next*/
        int nxtres=calc();
        if(nxtres<=ret) ret=nxtres;
        else if(exp((ret-nxtres)/T)>(double)rand()/RAND_MAX) /*backup*/
    }
}
int main()
{
    // freopen("simulate.in","r",stdin);
    // freopen("simulate.out","w",stdout);
    srand(time(NULL));
    srand(rand()^19260817);
    srand(rand()^20061112);
    srand(rand()^20070722);
    srand(rand());
    /*
    	readIn;
    */
    while((double)clock()/CLOCKS_PER_SEC<MAX_TIME) simulate();
    write(ret>>1);
    return 0;
}

高精度计算

我的评价是：不如 int128 。

是一个很头疼的版块，目前还不打算写。幸好能够支持 int128 所以还可以苟活一段时间。

跳舞链

较板，但是和网络流一样，重在构造。

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
int Le[MAXN],Ri[MAXN],Up[MAXN],Do[MAXN];
//十字链表的左右上下指针
int Cnt[MAXN],Row[MAXN],Col[MAXN];
//链表长度，行列信息
inline void init()
{
    for(re int i=0;i<=M;++i)
    {
        Le[i]=i-1,Ri[i]=i+1;
        Up[i]=Do[i]=i;
    }
    Le[0]=M,Ri[M]=0;
    Idx=M+1;
}
inline void add(int &he,int &ta,int x,int y)
{
    Row[Idx]=x,Col[Idx]=y,++Cnt[y];
    Up[Idx]=y,Do[Idx]=Do[y],Up[Do[y]]=Idx,Do[y]=Idx;
    Ri[he]=Le[ti]=Idx,Ri[Idx]=ta,Le[Idx]=he;
    ta=Idx++;
}
inline void remove(int p)	//删除
{
    Ri[Le[p]]=Ri[p],Le[Ri[p]]=Le[p];
    for(int i=Do[p];i!=p;i=Do[i])
        for(int j=Ri[i];j!=i;j=Ri[j])
        {
            --Cnt[Col[j]];
            Up[Do[j]]=Up[j],Do[Up[j]]=Do[j];
        }
}
inline void recover(int p)	//恢复
{
    for(int i=Up[p];i!=p;i=Up[i])
        for(int j=Le[i];j!=i;j=Le[j])
        {
            Up[Do[j]]=j,Do[Up[j]]=j;
            ++Cnt[Col[j]];
        }
    Ri[Le[p]]=p,Le[Ri[p]]=p;
}
相关文章