ACM模板

注：本文为个人向，有的是高中写的/网上找的，代码风格很奇怪

0 其他

0.1 vimrc

set ts=4 "tabstop
set sw=4 "shiftwidth
set sc "showcmd
set nu "number
set ru "ruler
set ai "autoindent
set mouse=a
filetype indent on

set et "expandtab
set smarttab
set autowrite

inoremap {<CR> {}<LEFT><CR><CR><UP><TAB>

map <F3> :w<CR>:!gdb %< -q <CR>
nmap <F4> :w<CR>:!g++ % -o %< -g -Wall -fsanitize=address <CR>
"imap <F4> <ESC>:w<CR>:!g++ % -o %< -g -Wall -fsanitize=address <CR>
nmap <F5> :w<CR>:!time ./%< <CR>
"imap <F5> <ESC>:w<CR>:!time ./%< <CR>

0.2 对拍

while true; do
    ./data > a.in
    ./a > a.out
    ./std > std.out
    if diff a.out std.out; then
        echo AC
    else
        exit 0
    fi
done

1 数据结构

1.1 线段树

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5;
int n,m,tot,root;
struct Tree{
	int l,r,ls,rs,sum,max,tag;
}t[N*2];
void push_up(int x)
{
	int L=t[x].ls,R=t[x].rs;
	t[x].sum=t[L].sum+t[R].sum;
	t[x].max=max(t[L].max,t[R].max);
}
void push_down(int x)
{
	if(t[x].tag)
	{
		int L=t[x].ls,R=t[x].rs,T=t[x].tag;t[x].tag=0;
	 	t[L].sum+=(t[L].r-t[L].l+1)*T;t[L].max+=T;t[L].tag+=T;
		t[R].sum+=(t[R].r-t[R].l+1)*T;t[R].max+=T;t[R].tag+=T;
	}
}
void Build(int &x,int L,int R)
{
	x=++tot;
	t[x].l=L;t[x].r=R;
	if(L==R)
		{scanf("%d",&t[x].sum);t[x].max=t[x].sum;return;}
	int mid=(L+R)>>1;
	Build(t[x].ls,L,mid);
	Build(t[x].rs,mid+1,R);
	push_up(x);
}
void Change(int x,int pos,int key)
{
	if(t[x].l==t[x].r)
		{t[x].sum=t[x].max=key;return;}
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(pos<=mid) Change(t[x].ls,pos,key);
	else Change(t[x].rs,pos,key);
	push_up(x);
}
void Add(int x,int L,int R,int key)
{
	if(L<=t[x].l&&R>=t[x].r)
		{t[x].sum+=(t[x].r-t[x].l+1)*key;t[x].max+=key;t[x].tag+=key;return;}
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(L<=mid) Add(t[x].ls,L,R,key);
	if(mid<R)  Add(t[x].rs,L,R,key);
	push_up(x);
}
int Sum(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].sum;
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1,sum=0;
	if(L<=mid) sum+=Sum(t[x].ls,L,R);
	if(R>mid)  sum+=Sum(t[x].rs,L,R);
	return sum;
}
int Max(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].max;
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1,mx=0;
	if(L<=mid) mx=max(mx,Max(t[x].ls,L,R));
	if(R>mid)  mx=max(mx,Max(t[x].rs,L,R));
	return mx;
}
int main()
{
	scanf("%d%d",&n,&m);
	Build(root,1,n);
	for(int i=1,t,x,y,z;i<=m;i++)
	{
		scanf("%d",&t);
		if(t==1)	  scanf("%d%d",&x,&y),Change(1,x,y);
		else if(t==2) scanf("%d%d%d",&x,&y,&z),Add(1,x,y,z);
		else if(t==3) scanf("%d%d",&x,&y),printf("%d\n",Sum(1,x,y));
		else scanf("%d%d",&x,&y),printf("%d\n",Max(1,x,y));
	}
}

1.2 树状数组

\(c_i = \sum\limits_{j=i-lowbit(i)+1}^{i} a_j = sum_i - sum_{i-lowbit(i)}\)

int Sum(int x){
	int sum=0;
	for(;x;x-=x&(-x)) sum+=c[x];
	return sum;
}
void Add(int x,int v){
	for(;x<=n;x+=x&(-x)) c[x]+=v;
}

1.3 树链剖分

#include<iostream>
#include<cstdio>
const int N=30010;
int n,Q,ans,tot,dep[N],fa[N],size[N],son[N],top[N],pos[N],a[N];
int head[N],next[N*2],to[N*2];
struct node{
	int l,r,ls,rs,max,sum;
}t[N*2];
void Dfs(int x)
{
	dep[x]=dep[fa[x]]+1;size[x]=1;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(y!=fa[x])
		{
			fa[y]=x;Dfs(y);
			size[x]+=size[y];
			if(size[y]>size[son[x]]) son[x]=y;
		}
}
void Dfs(int x,int f)
{
	pos[x]=++tot;top[x]=f;
	if(son[x]) Dfs(son[x],f);
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(y!=fa[x]&&y!=son[x])
			Dfs(y,y);
}
void push_up(int x)
{
	int L=t[x].ls,R=t[x].rs;
	t[x].sum=t[L].sum+t[R].sum;
	t[x].max=std::max(t[L].max,t[R].max);
}
void Build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	if(l==r) { t[x].max=t[x].sum=a[l];return; }
	int mid=(l+r)>>1;
	Build(t[x].ls=++tot,l,mid);
	Build(t[x].rs=++tot,mid+1,r);
	push_up(x);
}
void Change(int x,int num,int key)
{
	if(t[x].l==t[x].r) { t[x].max=t[x].sum=key;return; }
	int mid=(t[x].l+t[x].r)>>1;
	if(num<=mid) Change(t[x].ls,num,key);
	else Change(t[x].rs,num,key);
	push_up(x);
}
int Max(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].max;
	int mid=(t[x].l+t[x].r)>>1,num=-30001;
	if(L<=mid) num=std::max(num,Max(t[x].ls,L,R));
	if(R>mid)  num=std::max(num,Max(t[x].rs,L,R));
	return num;
}
int Sum(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].sum;
	int mid=(t[x].l+t[x].r)>>1,num=0;
	if(L<=mid) num+=Sum(t[x].ls,L,R);
	if(R>mid)  num+=Sum(t[x].rs,L,R);
	return num;
}
int GetMax(int x,int y)
{
	for(ans=-30001;top[x]!=top[y];x=fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
		ans=std::max(ans,Max(1,pos[top[x]],pos[x]));
	}
	if(pos[x]>pos[y]) std::swap(x,y);
	return std::max(ans,Max(1,pos[x],pos[y]));
}
int GetSum(int x,int y)
{
	for(ans=0;top[x]!=top[y];x=fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
		ans+=Max(1,pos[top[x]],pos[x]);
	}
	if(pos[x]>pos[y]) std::swap(x,y);
	return ans+Max(1,pos[x],pos[y]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,ecnt=0,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		to[++ecnt]=y;next[ecnt]=head[x];head[x]=ecnt;
		to[++ecnt]=x;next[ecnt]=head[y];head[y]=ecnt;
	}
	Dfs(1);Dfs(1,1);
	for(int i=1;i<=n;i++) scanf("%d",&a[pos[i]]);
	Build(tot=1,1,n);
	scanf("%d",&Q);char s[10];
	for(int i=1,x,y;i<=Q;i++)
	{
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='C') Change(1,pos[x],y);
		else if(s[1]=='M') printf("%d\n",GetMax(x,y));
		else printf("%d\n",GetSum(x,y));
	}
}

1.4 SBT

#include<cstdio>
using namespace std;
const int N=1e5+5;
int tot,root,key[N],size[N],son[N][2];
void Rotate(int &x,bool flag) //0->left_rotate 1->right_rotate
{
	int y=son[x][!flag];
	son[x][!flag]=son[y][flag];
	son[y][flag]=x;
	size[y]=size[x];
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
	x=y;
}
void Maintain(int &x,bool flag) //0->ls 1-> rs
{
	if(size[son[son[x][flag]][flag]]>size[son[x][!flag]])
	  Rotate(x,!flag);
	else if(size[son[son[x][flag]][!flag]]>size[son[x][!flag]])
	  Rotate(son[x][flag],flag),Rotate(x,!flag);
	else return;
	Maintain(son[x][0],0);
	Maintain(son[x][1],1);
	Maintain(x,1);
	Maintain(x,0); 
}
void Insert(int &x,int y)
{
	if(!x)
	{
		x=++tot;
		key[x]=y;
		size[x]=1;
		son[x][0]=son[x][1]=0;
		return;
	}
	size[x]++;
	if(y<=key[x]) Insert(son[x][0],y);
	else Insert(son[x][1],y);
	Maintain(x,y>key[x]);
}
int Delete(int &x,int y)
{
	size[x]--;
	if((y<key[x]&&!son[x][0])||(y>key[x]&&!son[x][1])) return 0;
	if(y==key[x])
	{
		int ans=key[x];
		if(!son[x][0]||!son[x][1]) x=son[x][0]+son[x][1];
		else
		{
			int k=son[x][0]; while(son[k][1]) k=son[k][1]; 
			key[x]=Delete(son[x][0],key[k]);
		}
		return ans;
	}
	if(y<key[x]) return Delete(son[x][0],y);
	else return Delete(son[x][1],y);
}
int Find(int x,int y)
{
	if(!x) return 0;
	if(y==key[x]) return 1;
	else if(y<key[x]) return Find(son[x][0],y);
	else return Find(son[x][1],y);
}
int Rank(int x,int y)
{
	if(!x) return 1;
	else if(y<=key[x]) return Rank(son[x][0],y);
	else return size[son[x][0]]+1+Rank(son[x][1],y);
}
int Kth(int x,int y)
{
	if(y==size[son[x][0]]+1) return key[x];
	else if(y<=size[son[x][0]]) return Kth(son[x][0],y);
	else return Kth(son[x][1],y-size[son[x][0]]-1);
}
int Pred(int &x,int y)
{
	if(!x) return y;
	if(y<=key[x]) return Pred(son[x][0],y);
	else
	{
		int ans=Pred(son[x][1],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
int Succ(int &x,int y)
{
	if(!x) return y;
	if(y>=key[x]) return Succ(son[x][1],y);
	else
	{
		int ans=Succ(son[x][0],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
void Inorder(int x)
{
	if(x)
	{
		Inorder(son[x][0]);
		printf("%d ",key[x]);
		Inorder(son[x][1]);
	}
}
int main()
{
	int x,y;
	while(scanf("%d%d",&x,&y)!=EOF)
	{
		if(x==1) Insert(root,y);
		else if(x==2) Delete(root,y);
		else if(x==3) printf("%d\n",Find(root,y));
		else if(x==4) printf("%d\n",Rank(root,y));
		else if(x==5) printf("%d\n",Kth(root,y));
		else if(x==6) printf("%d\n",Pred(root,y));
		else printf("%d\n",Succ(root,y));
		//if(x<=2) Inorder(root),printf("\n");
	}
}

1.5 splay

#include<cstdio>
const int N=1e5+5;
int tot,root,size[N],num[N],key[N],fa[N],son[N][2];
void push_up(int x)
{
	size[x]=size[son[x][0]]+size[son[x][1]]+num[x];
}
void Rotate(int x)
{
	//push_down(fa[x]);push_down(x); 
	int y=fa[x],z=fa[y],t=(son[y][0]==x);
	if(z) son[z][son[z][1]==y]=x;fa[x]=z;
	son[y][!t]=son[x][t];fa[son[y][!t]]=y;
	son[x][t]=y;fa[y]=x;
	push_up(y);push_up(x);
}
void Splay(int x,int f)
{
	while(fa[x]!=f)
	{
		int y=fa[x],z=fa[y];
		if(z!=f)
		{
			if(son[z][0]==y^son[y][0]==x) Rotate(x);
			else Rotate(y);
		} 
		Rotate(x);	
	}
	if(!f) root=x;
}
void Insert(int &x,int v,int f)
{
	if(!x)
	{
		x=++tot;
		son[x][0]=son[x][1]=0;
		size[x]=num[x]=1;
		key[x]=v;fa[x]=f;
		Splay(x,0);
		return;
	}
	if(v==key[x])
	{
		num[x]++;size[x]++;
		Splay(x,0);
		return;
	}
	Insert(son[x][v>key[x]],v,x);
	push_up(x);
}
int Get(int v)
{
	int x=root;
	while(x&&v!=key[x]) x=son[x][v>key[x]];
	return x;
}
void Delete(int x)
{
	x=Get(x);if(!x) return;
	Splay(x,0);
	if(num[x]>1) {num[x]--;size[x]--;return;}
	if(!son[x][0]||!son[x][1]) root=son[x][0]+son[x][1];
	else
	{
		int y=son[x][1];while(son[y][0]) y=son[y][0];
		Splay(y,x);
		son[y][0]=son[x][0];fa[son[y][0]]=y;
		root=y;
	}
	fa[root]=0;
	push_up(root);
}
int Rank(int v)
{
	Insert(root,v,0);
	int ans=size[son[root][0]]+1;
	Delete(v);
	return ans;
}
int Kth(int x)
{
	int y=root;
	while(x<=size[son[y][0]]||x>size[son[y][0]]+num[y])
	{
		if(x<=size[son[y][0]]) y=son[y][0];
		else x-=size[son[y][0]]+num[y],y=son[y][1];
	}
	return key[y];
}
int Pred(int v)
{
	Insert(root,v,0);
	int x=son[root][0];while(son[x][1]) x=son[x][1];
	Delete(v);
	return key[x];
}
int Succ(int v)
{
	Insert(root,v,0);
	int x=son[root][1];while(son[x][0]) x=son[x][0];
	Delete(v);
	return key[x];
}
void Inorder(int x)
{
	if(son[x][0]) Inorder(son[x][0]);
	for(int i=1;i<=num[x];i++) printf("%d ",key[x]);
	if(son[x][1]) Inorder(son[x][1]);
}
int main()
{
	for(int x,y;scanf("%d%d",&x,&y)!=EOF;)
	{
		if(x==1) Insert(root,y,0);
		else if(x==2) Delete(y);
		else if(x==3) printf("%d\n",Get(y));
		else if(x==4) printf("%d\n",Rank(y));
		else if(x==5) printf("%d\n",Kth(y));
		else if(x==6) printf("%d\n",Pred(y));
		else printf("%d\n",Succ(y));
		//if(x<=2) Inorder(root),printf("\n");
	}
}

1.6 LCT

#include <iostream>
#include <cstdio>
const int N=1e5;
int n,m,fa[N],son[N][2],size[N],key[N],sum[N],max[N],tag[N],rev[N];
bool isroot(int x)
{
	return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void Add(int x,int v)
{
	key[x]+=v;sum[x]+=v*size[x];max[x]+=v;tag[x]+=v;
}
void push_up(int x)
{
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
	sum[x]=sum[son[x][0]]+sum[son[x][1]]+key[x];
	max[x]=std::max(std::max(max[son[x][0]],max[son[x][1]]),key[x]);
}
void push_down(int x)
{
	if(rev[x]) rev[x]^=1,rev[son[x][0]]^=1,rev[son[x][1]]^=1,std::swap(son[x][0],son[x][1]);
	if(tag[x]) Add(son[x][0],tag[x]),Add(son[x][1],tag[x]),tag[x]=0;
}
void Rotate(int x)
{
	push_down(fa[x]);push_down(x);
	int y=fa[x],z=fa[y],t=(son[y][0]==x);
	if(!isroot(y)) son[z][son[z][1]==y]=x;fa[x]=z;
	son[y][!t]=son[x][t];fa[son[y][!t]]=y;
	son[x][t]=y;fa[y]=x;
	push_up(y);push_up(x);
}
void Splay(int x)
{
	push_down(x);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(son[z][0]==y^son[y][0]==x) Rotate(x);
		    else Rotate(y);
		}  
		Rotate(x);
	}
}
void Access(int x) //将x到root的路径变成实路径
{
	for(int y=0;x;y=x,x=fa[x]) Splay(x),son[x][1]=y,push_up(x);
}
void Makeroot(int x) //将x变为root
{
	Access(x);Splay(x);rev[x]^=1;
}
void Split(int x,int y) //将x到y的路径放入splay，x为根
{
	Makeroot(x);Access(y);Splay(x);
}
void Link(int x,int y)
{
	Makeroot(x);fa[x]=y;
}
void Cut(int x,int y)
{
	Split(x,y);son[x][1]=fa[y]=0;
}
int Find(int x) //找到x所在树的root
{
	Access(x);Splay(x);while(son[x][0]) x=son[x][0];return x;
}
int main()
{
	max[0]=-0x7fffffff;
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)
	  scanf("%d",&x),size[i]=1,Add(i,x),tag[i]=0;
	for(int i=1,opt,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) Link(x,y);
		else if(opt==2) Cut(x,y);
		else if(opt==3) Splay(x),key[x]=y,push_up(x); //更改x的权值为y
		else if(opt==4) Split(x,y),printf("%d\n",max[x]); //求x到y路径上的最大值
		else if(opt==5) Split(x,y),printf("%d\n",sum[x]); //求x到y路径上的和
		else if(opt==6) printf("%d\n",Find(x)==Find(y));  //判断x和y是否连通
		else scanf("%d",&z),Split(x,y),Add(x,z);  //将x到y路径上加z
	}
}

1.7 主席树

#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,tot,totn,a[N],b[N],root[N],size[N*20],ls[N*20],rs[N*20];
void Insert(int l,int r,int x,int &y,int v)
{
	y=++tot;
	size[y]=size[x]+1;
	ls[y]=ls[x];rs[y]=rs[x];
	if(l==r) return;
	int mid=(l+r)>>1;
	if(v<=mid) Insert(l,mid,ls[x],ls[y],v);
	else Insert(mid+1,r,rs[x],rs[y],v);
}
int Quary(int l,int r,int x,int y,int v)
{
	if(l==r) return l;
	int mid=(l+r)>>1,k=size[ls[y]]-size[ls[x]];
	if(v<=k) return Quary(l,mid,ls[x],ls[y],v);
	else return Quary(mid+1,r,rs[x],rs[y],v-k);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	totn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
	  Insert(1,totn,root[i-1],root[i],lower_bound(b+1,b+totn+1,a[i])-b);
	for(int i=1,x,y,z;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),printf("%d\n",b[Quary(1,totn,root[x-1],root[y],z)]);
}

2 字符串

读入一行 `cin.getline(s, 1005, '');' 或 'fgets(s, 1005, stdin);'

2.1 KMP

#include<cstring>
#include<cstdio>
int n,m,next[100001];
char a[100001],b[100001];
void Getnext()
{
	next[0]=-1;
	for(int i=1,j=0;i<m;i++,j++)
	{
		while(j!=-1&&b[i]!=b[j]) j=next[j];
		next[i+1]=j+1;
	}
}
void KMP()
{
	for(int i=0,j=0;i<n;i++,j++)
	{
		while(j!=-1&&a[i]!=b[j]) j=next[j];
		if(j==m-1) printf("%d\n",i-j+1);
	}
}
int main()
{
	scanf("%s%s",a,b); //a->long b->short
	n=strlen(a);m=strlen(b);
	Getnext();
	KMP();
}

2.2 后缀数组

DC3 记得在字符串后面加一位比出现字符都小的字符

#include<cstdio>
const int N=10001;
int r[N],sa[N],a[N],b[N],v[N],s[N],rank[N],height[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=r[i]]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[x[i]]]=i;
	for(j=1,p=1;p<n;j*=2,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<n;i++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=0;i<n;i++) rank[sa[i]]=i;
	for(i=0;i<n-1;height[rank[i++]]=k)
	  for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

倍增LCP

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int base=29;
int n,sa[10001];
char s[10001];
unsigned long long ha[10001],power[10001]={1};
unsigned long long HASH(int l,int r)
{
	return ha[r]-ha[l-1]*power[r-l+1];
}
int LCP(int x,int y)
{
	int l=0,r=std::min(n-x+1,n-y+1),mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(HASH(x,x+mid-1)==HASH(y,y+mid-1)) l=mid; else r=mid-1;
	}
	return l;
}
bool cmp(int x,int y)
{
	int z=LCP(x,y);return s[x+z]<s[y+z];
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	  ha[i]=ha[i-1]*base+s[i]-'a'+1,power[i]=power[i-1]*base,sa[i]=i;
	std::sort(sa+1,sa+n+1,cmp);
	for(int i=2;i<=n;i++) height[i]=LCP(sa[i-1],sa[i]);
}

2.3 SAM后缀自动机

#include <cstring>
#include <cstdio>
const int N=10005;
char s[N];
int last,cnt,n,len[N<<1],fa[N<<1],son[N<<1][26];
void Add(int x)
{
	int c=s[x]-'a',p=last,np=++cnt;
	len[last=np]=x;
	for(;p&&!son[p][c];p=fa[p]) son[p][c]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=son[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			memcpy(son[nq],son[q],sizeof son[q]);
			fa[nq]=fa[q];
			fa[np]=fa[q]=nq;
			for(;son[p][c]==q;p=fa[p]) son[p][c]=nq;
		}
	}
}
int main()
{
	scanf("%s",s+1);
	last=cnt=1;
	n=strlen(s+1);
	for(int i=1;i<=n;i++) Add(i);
}

struct NODE{
	int par, go[cL];
	int len,s;
}nodes[maxn*2];
int cn=1;
int root, last;
struct LIST{
	int v;
	int next;
}list[maxn*2];
int cl=1,head[maxn];
void addList(int v, int h){
	list[cl]=(LIST){v,head[h]};
	head[h]=cl++;
}
int newNode(int len,int s){
	int ret = cn++;
	nodes[ret].len=len;
	nodes[ret].s=s;
	nodes[ret].par=0;
	memset(nodes[ret].go,0,sizeof(nodes[ret].go));
	addList(ret, len);
	return ret;
}
void extend(int w){
	int p=last, np=newNode(nodes[p].len+1,1);
	while(p && !nodes[p].go[w]){
		nodes[p].go[w] = np;
		p=nodes[p].par;
	}
	if(!p){
		nodes[np].par = root;
	}else{
		int q = nodes[p].go[w];
		if(nodes[p].len + 1 == nodes[q].len){
			nodes[np].par=q;
		}else{
			int nq = newNode(nodes[p].len+1,0);
			memcpy(nodes[nq].go, nodes[q].go, sizeof(nodes[nq].go));
			nodes[nq].par = nodes[q].par;
			nodes[q].par = nq;
			nodes[np].par = nq;
			while(p && nodes[p].go[w] == q){
				nodes[p].go[w] = nq;
				p=nodes[p].par;
			}
		}
	}
	last=np;
}

2.4 AC自动机

#include <cstring>
#include <cstdio>
#include <queue>
const int N=500005;
int T,n,tot,end[N],fail[N],son[N][26];
char s[N*2];
std::queue<int> Q;
void init(int x)
{
	end[x]=0;
	for(int i=0;i<26;i++) son[x][i]=0;
}
void Add()
{
	scanf("%s",s);
	int len=strlen(s),pre=0;
	for(int i=0;i<len;i++)
	{
		if(!son[pre][s[i]-'a'])
		  init(son[pre][s[i]-'a']=++tot);
		pre=son[pre][s[i]-'a'];
	}
	end[pre]++;
}
void Build()
{
	Q.push(0);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<26;i++)
		{
			if(son[x][i])
			{
				Q.push(son[x][i]);
				fail[son[x][i]]=x?son[fail[x]][i]:0;
			}
			else son[x][i]=x?son[fail[x]][i]:0;
		}
	}
}
int Calc()
{
	scanf("%s",s);
	int len=strlen(s),pre=0,ans=0;
	for(int i=0;i<len;i++)
	{
		pre=son[pre][s[i]-'a'];
		for(int j=pre;j;j=fail[j])
		  ans+=end[j],end[j]=0;
	}
	return ans;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init(tot=0);
		for(scanf("%d",&n);n;n--) Add();
		Build();
		printf("%d\n",Calc());
	}
}

2.5 Manacher

#include <iostream>
#include <cstring>
#include <cstdio>
int n,m,maxpos,maxlen,len[200001];
char s[100001],a[200001];
int main()
{
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++) a[m++]='#',a[m++]=s[i];
	a[m++]='#';maxlen=-1;
	for(int i=0,j;i<m;i++)
	{
		j=std::min(len[maxpos*2-i],maxlen-i)*(i<=maxlen);
		while(i-j>=0&&i+j<=m&&a[i-j]==a[i+j]) j++;
		len[i]=j-1;
		if(i+j>maxlen) maxpos=i,maxlen=i+j;
	}
	for(int i=0;i<m;i++) printf("%d ",len[i]);
}

2.6 回文树

#include <cstring>
#include <cstdio> 
using namespace std;
const int N=1e6;
int n,LEN,tot,last,son[N][26],fail[N],len[N],num[N];
char s[N];
int newnode(int l)
{
	len[++tot]=l;
	return tot;
}
int getnode(int x)
{
	while(s[n-len[x]-1]!=s[n]) x=fail[x];
	return x;
}
void Add(int c)
{
	int cnt=getnode(last);
	if(!son[cnt][c])
	{
		int now=newnode(len[cnt]+2);
		fail[now]=son[getnode(fail[cnt])][c];
		son[cnt][c]=now;
	}
	num[last=son[cnt][c]]++;
}
int main()
{
	scanf("%s",s+1);
	LEN=strlen(s+1);
	newnode(-1);fail[0]=1;
	while(++n<=LEN) Add(s[n]-'a');
	for(int i=tot;i>=2;i--) num[fail[i]]+=num[i];
}

3 数学

3.1 数论

3.1.1 中国剩余定理

\(x \equiv a_i \pmod{m_i}\) 的解为 \(x=\sum\limits_{i=1}^na_it_iM_i\pmod{M}\).其中\(M=\prod\limits_{i=1}^nm_i\), \(M_i=\frac{M}{m_i}\), \(t_i=M_i^{-1}\pmod{m_i}\).

3.1.2 lucas定理

\(C(n,m) \bmod p = C(n\div p,m\div p) \times C(n\bmod p,m\bmod p)\).

3.1.3 欧拉定理

\(a^{\varphi(n)} \equiv 1 \pmod{n}\).

3.1.4 莫比乌斯反演

\(\mu(d)\) 的定义：
(1) 若 \(d=1\)，则\(\mu(d)=1\)
(2) 若 \(d=p_1p_2\dots p_k\)，\(p_i\)为互异素数，则\(\mu(d)=(-1)^k\)
(3) 其他情况下 \(\mu(d)=0\)

莫比乌斯反演：
\(F(n)=\sum\limits_{d|n} f(d) \Rightarrow f(n)=\sum\limits_{d|n}\mu(d) F(\frac{n}{d}).\)
\(F(n)=\sum\limits_{n|d} f(d) \Rightarrow f(n)=\sum\limits_{n|d}\mu(\frac{d}{n}) F(d).\)

3.1.5 快速幂

int power(int a,int b,int P)
{
	int re=1;
	for(;b;b>>=1,a=(long long)a*a%P)
		if(b&1) re=(long long)re*a%P;
	return re;
}

3.1.6 exgcd

#include <cstdio>
using namespace std;
int a,b,c,d,x,y;
void exgcd(int a,int b,int &d,int &x,int &y)
{
	if(!b) d=a,x=1,y=0;
	else exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	exgcd(a,b,d,x,y);
	if(!(c%d))
	{
		x*=c/d;y*=c/d;a/=d;b/=d;
		for(int k=-2;k<=2;k++)
		printf("%d %d\n",x+k*b,y-k*a);
	}
}

3.1.7 欧拉筛法

\(phi[x]\) : \(1\)~\(x\)中与\(x\)互质的数的个数 \(phi[x]=x\times \prod\limits_{p|x} \frac{p-1}{p}\)
\(d[x]\) : \(x\)的因数的个数 \(d[x]=\prod\limits_{p|x} (p+1)\)
\(e[x]\) : \(x\)的最小素因子的个数
\(mu[x]\) : 莫比乌斯函数

#include<cstdio>
const int N = 10001;
int totp, prime[N], phi[N], d[N], e[N], mu[N];
bool not_p[N];
void init() {
  not_p[1] = 1;
  d[1] = e[1] = mu[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!not_p[i]) {
      prime[++totp] = i;
      phi[i] = i - 1;
      d[i] = 2;
      e[i] = 1;
      mu[i] = -1;
    }
    for (int j = 1; j <= totp && prime[j] * i < N; ++j) {
      int p = prime[j], pi = prime[j] * i;
      not_p[pi] = 1;
      if (i % p) {
        phi[pi] = phi[i] * phi[p];
        d[pi] = d[i] * d[p];
        e[pi] = 1;
        mu[pi] = -mu[i];
      } else {
        phi[pi] = phi[i] * p;
        d[pi] = d[i] / (e[i] + 1) * (e[i] + 2);
        e[pi] = e[i] + 1;
        mu[pi] = 0;
        break;
      }
    }
  }
}

LL Phi(LL x) 
{
	LL i,re=x;
	for(i=2;i*i<=x;i++)
	  if(x%i==0)
		{
			re/=i;
			re*=i-1;
			while(x%i==0)
				x/=i;
		}
	if(x!=1)
		re/=x,re*=(x-1);
	return re;
}

/*
100内的质数：
  2,   3,   5,   7,  11,  13,  17,  19,  23,  29,
 31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
 73,  79,  83,  89,  97.
质数原根：
998244353  = 119 * 2 ^ 23, g = 3
1004535809 = 479 * 2 ^ 21, g = 3
2013265921 =  15 * 2 ^ 27, g = 31
2281701377 =  17 * 2 ^ 27, g = 3
前20个数：
num     is_p    phi     d       e       mu
1       0       0       1       1       1
2       1       1       2       1       -1
3       1       2       2       1       -1
4       0       2       3       2       0
5       1       4       2       1       -1
6       0       2       4       1       1
7       1       6       2       1       -1
8       0       4       4       3       0
9       0       6       3       2       0
10      0       4       4       1       1
11      1       10      2       1       -1
12      0       4       6       2       0
13      1       12      2       1       -1
14      0       6       4       1       1
15      0       8       4       1       1
16      0       8       5       4       0
17      1       16      2       1       -1
18      0       6       6       1       0
19      1       18      2       1       -1
20      0       8       6       2       0
*/

3.1.8 求质因子

Miller_Rabin & Pollard_rho

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
int power(int a,int b,int P)
{
	int c=1;
	for(;b;b>>=1,a=(long long)a*a%P)
		if(b&1) c=(long long)c*a%P;
	return c;
}
bool Prime(int base,int x)
{
	if(base==x) return 1;
	for(int i=x-1;;i>>=1)
	{
		int y=power(base,i,x);
		if(y==x-1) return 1;
		if(y!=1) return 0;
		if(i&1) return 1;
	}
}
bool Miller_Rabin(int x)
{
	if(x==2) return 1;
	if(x<2||!(x&1)) return 0;
	for(int i=1;i<=10;i++)
		if(!Prime(rand()%(x-1)+1,x))
			return 0;
	return 1;
} 
int gcd(int x,int y)
{
	return !y?x:gcd(y,x%y);
}
int Pollard_rho(int n,int a)
{
	for(int i=1,k=1,x=rand()%n,y=x;;i++)
	{
		x=((long long)x*x%n+a)%n;
		int d=gcd(abs(y-x),n);
		if(d>1&&d<n) return d;
		if(x==y) return n;
		if(i==k) y=x,k<<=1;
	}
}
void findfac(int n)
{
	if(Miller_Rabin(n))
	{ 
		printf("%d ",n);return;
	}
	int p=n;
	while(p>=n) p=Pollard_rho(p,rand()%(n-1)+1);
	findfac(p);findfac(n/p);
}
int main()
{
	std::srand(time(NULL));
	int n;
	while(scanf("%d",&n))
		findfac(n),printf("\n");
}

3.1.9 FFT

#include <complex>
#include <cstdio>
const double pi=acos(-1);
int len1,len2,n,m,rev[262200];
std::complex<double> a[262200],b[262200];
void FFT(std::complex<double> *a,int f)
{
	for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1)
	{
		std::complex<double> wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<n;j+=(i<<1))
		{
			std::complex<double> w(1,0);
			for(int k=0;k<i;k++,w*=wn)
			{
				std::complex<double> x=a[j+k],y=a[j+k+i]*w;
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&len1,&len2);
	for(int i=0;i<=len1;i++) scanf("%lf",&a[i].real());
	for(int i=0;i<=len2;i++) scanf("%lf",&b[i].real());
	for(n=1,m=0;n<=len1+len2;n<<=1,m++);
    // m=ceil(log(len1+len2+1)/log(2)),n=1<<m;
	for(int i=0;i<n;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(m-1);
	FFT(a,1);FFT(b,1);
	for(int i=0;i<n;i++) a[i]*=b[i];
	FFT(a,-1);
	for(int i=0;i<=len1+len2;i++) printf("%d ",(int)(a[i].real()/n+0.1));
}

typedef complex<double> cmplx;
double Pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172;
void rev_inc(int &v,int n){
	n>>=1;
	while(v&n){v^=n;n>>=1;}
	v^=n;
}
void DFT(cmplx *a,int len,int dir){
	int n=1<<len;
	for(int i=1,j=n>>1;i<n;++i,rev_inc(j,n)) if(i<j) swap(a[i],a[j]);
	for(int i=0;i<len;++i){
		int m=1<<i;
		cmplx wm(cos(Pi/m),dir*sin(Pi/m));
		for(int j=0;j<n;j+=(m<<1)){
			cmplx w(1);
			for(int k=0;k<m;++k){
				cmplx u=a[j+k],t=w*a[j+k+m];
				a[j+k]=u+t;
				a[j+k+m]=u-t;
				w*=wm;
			}
		}
	}
	if(dir==-1) for(int i=0;i<n;++i) a[i]/=n;
}
void multiply(cmplx *a,cmplx *b,int n,cmplx *c){
	int l=log2(n-1)+2;
	n=1<<l;
	DFT(a,l,1);
	DFT(b,l,1);
	for(int i=0;i<n;++i) c[i]=a[i]*b[i];
	DFT(c,l,-1);
	for(int i=0;i<n;++i) a[i]=b[i]=0;
}

3.1.10 NTT

#include <iostream>
#include <cstdio>
#define Inv(x) (power(x,P-2))
const int P=(479<<21)+1;
const int G=3;
int len1,len2,n,m,rev[262200],a[262200],b[262200];
int power(int x,int y)
{
	int z=1;
	for(;y;y>>=1,x=(long long)x*x%P)
		if(y&1) z=(long long)z*x%P;
	return z;
}
void NTT(int *a,int f)
{
	for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
	for(int i=1,t=1;i<n;i<<=1,t++)
	{
		int wn=power(G,(P-1)/(1<<t));
		if(f==-1) wn=Inv(wn);
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0,w=1;k<i;k++,w=(long long)w*wn%P)
			{
				int x=a[j+k],y=(long long)a[j+k+i]*w%P;
				a[j+k]=(x+y)%P;a[j+k+i]=(x-y+P)%P;
			}
	}
}
int main()
{
	scanf("%d%d",&len1,&len2);
	for(int i=0;i<=len1;i++) scanf("%d",&a[i]);
	for(int i=0;i<=len2;i++) scanf("%d",&b[i]);
	for(n=1,m=0;n<=len1+len2;n<<=1,m++);
	for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1)<<(m-1);
	NTT(a,1);NTT(b,1);
	for(int i=0;i<n;i++) a[i]=(long long)a[i]*b[i]%P;
	NTT(a,-1);n=Inv(n);
	for(int i=0;i<=len1+len2;i++) printf("%lld ",(long long)a[i]*n%P);
}

3.1.11 FWT

void FWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
                //xor:a[i+j]=x+y,a[i+j+d]=x-y;
                //and:a[i+j]=x+y;
                //or:a[i+j+d]=x+y;
            }
}
void UFWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
                //and:a[i+j]=x-y;
                //or:a[i+j+d]=y-x;
            }
}
void solve(int a[],int b[],int n)
{
    FWT(a,n);
    FWT(b,n);
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
    UFWT(a,n);
}

3.1.12 BM

#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
#define rep(i, a, n) for (int i=a;i<n;i++)
#define per(i, a, n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
const ll mod = 1000000007;

ll pow(ll a, ll b) {
  ll res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1)res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}

namespace linear_seq {
  VI BM(VI s) {
    VI C(1, 1), B(1, 1);
    int L = 0, m = 1, b = 1;
    rep(n, 0, SZ(s)) {
      ll d = 0;
      rep(i, 0, L + 1) d = (d + (ll) C[i] * s[n - i]) % mod;
      if (d == 0) ++m;
      else if (2 * L <= n) {
        VI T = C;
        ll c = mod - d * pow(b, mod - 2) % mod;
        while (SZ(C) < SZ(B) + m) C.pb(0);
        rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
        L = n + 1 - L;
        B = T;
        b = d;
        m = 1;
      } else {
        ll c = mod - d * pow(b, mod - 2) % mod;
        while (SZ(C) < SZ(B) + m) C.pb(0);
        rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
        ++m;
      }
    }
    printf("f(n) = ");
    rep(i, 1, SZ(C)) printf("%lldf(n-%d)%s", (mod - C[i]) % mod, i, i + 1 == SZ(C) ? "\n" : " + ");
    return C;
  }

  const int N = 10010;
  ll res[N], _md[N];
  vector<int> Md;
  void mul(ll *a, ll *b, int k) {
    ll _c[N];
    rep(i, 0, k + k) _c[i] = 0;
    rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
    for (int i = k + k - 1; i >= k; i--)
      if (_c[i])
        rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
    rep(i, 0, k) a[i] = _c[i];
  }
  int solve(ll n, VI a, VI b)   // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
  {
    //printf("%d\n",SZ(b));
    ll ans = 0, pnt = 0;
    int k = SZ(a);
    assert(SZ(a) == SZ(b));
    rep(i, 0, k) _md[k - 1 - i] = -a[i];
    _md[k] = 1;
    Md.clear();
    rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
    rep(i, 0, k) res[i] = 0;
    res[0] = 1;
    while ((1ll << pnt) <= n) pnt++;
    for (int p = pnt; p >= 0; p--) {
      mul(res, res, k);
      if ((n >> p) & 1) {
        for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
        res[0] = 0;
        rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
      }
    }
    rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
    if (ans < 0) ans += mod;
    return ans;
  }

  int gao(VI a, ll n) {
    VI c = BM(a);
    c.erase(c.begin());
    rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
    return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
  }
};

int main() {
  int x, y;
  VI a, b;
  for (scanf("%d", &x); x; --x) scanf("%d", &y), a.pb(y);
  b = linear_seq::BM(a);
  b.erase(b.begin());
  rep(i, 0, SZ(b)) b[i] = (mod - b[i]) % mod;
  for (int i = 0; i < 20; ++i)
    printf("%d: %d\n", i, linear_seq::solve(i, b, VI(a.begin(), a.begin() + SZ(b))));
  /*
  int t, n;
  for (scanf("%d", &t); t; t--) {
    scanf("%d", &n);
    printf("%d\n", linear_seq::gao(VI{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}, n - 1));
  }
  */
}

3.2 组合数学

3.3 计算几何

3.3.1 凸包

#include <algorithm>
#include <cstdio>
#include <cmath>
const int N=1e5+5;
const double eps=1e-6;
int n,top;
double len,S;
struct Point { double x,y; } a[N],b[N];
double dis(Point x,Point y)
{
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double Cross(Point x,Point y,Point z)
{
	return (x.x-z.x)*(y.y-z.y)-(x.y-z.y)*(y.x-z.x);
}
double Cross(Point x,Point y)
{
	return x.x*y.y-x.y*y.x;
}
bool cmp(const Point &x,const Point &y)
{
	double t=Cross(x,y,a[1]);return abs(t)>eps?t>0:dis(a[1],x)<dis(a[1],y);
}
void Graham()
{
	int t=1;
	for(int i=2;i<=n;i++)
	  if(a[i].x<a[t].x||(a[i].x==a[t].x&&a[i].y<a[t].y)) t=i;
	if(t!=1) std::swap(a[t],a[1]);
	std::sort(a+2,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&Cross(a[i],b[top],b[top-1])>=0) top--;
		b[++top]=a[i];
	}
	b[top+1]=b[1];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	Graham();
	for(int i=1;i<=top;i++) len+=dis(b[i],b[i+1]);
	printf("L: %.8lf\n",len);
	for(int i=1;i<=top;i++) S+=Cross(b[i],b[i+1]);
	printf("S: %.8lf\n",S/2);
}

3.3.2 半平面交

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,cnt,tot;
struct node1 {   double x,y;   }  p[55],a[505];
struct node2 {   node1 a,b; double k;   }  l[505],q[505];
node1 operator -(node1 a,node1 b)
{   node1 t;t.x=a.x-b.x;t.y=a.y-b.y;return t;   }
double operator *(node1 a,node1 b)
{   return a.x*b.y-a.y*b.x;   }
bool operator <(node2 a,node2 b)
{   return a.k==b.k?(a.b-a.a)*(b.b-a.a)<0:a.k<b.k;   }
node1 Inter(node2 a,node2 b)
{
	double k1,k2,t;
	k1=(b.b-a.a)*(a.b-a.a);
	k2=(a.b-a.a)*(b.a-a.a);
	t=k1/(k1+k2);
	node1 ans;
	ans.x=b.b.x+(b.a.x-b.b.x)*t;
	ans.y=b.b.y+(b.a.y-b.b.y)*t;
	return ans;
}
bool jud(node2 a,node2 b,node2 c)
{
	return (c.b-c.a)*(Inter(a,b)-c.a)<0;
}
double calc()
{
	sort(l+1,l+cnt+1);
	int L=1,R=0;
	for(int i=1;i<=cnt;i++)
	  if(l[i].k!=l[i-1].k) l[++tot]=l[i];
	for(int i=1;i<=tot;i++)
	{
		while(L<R&&jud(q[R-1],q[R],l[i])) R--;
		while(L<R&&jud(q[L+1],q[L],l[i])) L++;
		q[++R]=l[i];
	}
	while(L<R&&jud(q[R-1],q[R],l[L])) R--;
	while(L<R&&jud(q[L+1],q[L],l[R])) L++;
	q[R+1]=q[L];tot=0;
	for(int i=L;i<=R;i++) a[++tot]=Inter(q[i],q[i+1]);
	a[++tot]=a[1];
	if(tot<3) return 0;
	double ans=0;
	for(int i=1;i<=tot;i++) ans+=a[i]*a[i+1];
	return fabs(ans)/2;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,k;i<=n;i++)
	{
		scanf("%d",&k);
		for(int j=1;j<=k;j++) scanf("%lf%lf",&p[j].x,&p[j].y);
		p[k+1]=p[1];
		for(int j=1;j<=k;j++) l[++cnt].a=p[j],l[cnt].b=p[j+1];
	}
	for(int i=1;i<=cnt;i++)
	  l[i].k=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
	printf("%.3lf",calc());
}

3.3.3 旋转卡壳

求最远点对距离

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,top;
struct node{
	int x,y;
}a[50005],b[50005];
node operator -(node a,node b)
{
	node t;
	t.x=a.x-b.x;t.y=a.y-b.y;
	return t;
}
int operator *(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}
int dis(node a,node b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool operator <(node aa,node bb)
{
	int t=(aa-a[1])*(bb-a[1]);
	return (!t)?dis(aa,a[1])<dis(bb,a[1]):t>0;
}
void Graham()
{
	int k=1;
	for(int i=2;i<=n;i++)
	  if(a[i].x<a[k].x||(a[i].x==a[k].x)&&a[i].y<a[k].y) k=i;
	if(k!=1) swap(a[k],a[1]);
	sort(a+2,a+n+1);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&(a[i]-b[top-1])*(b[top]-b[top-1])>=0) top--;
		b[++top]=a[i];
	}
	b[top+1]=b[1];
}
int Calc()
{
	int q=2,ans=0;
	for(int i=1;i<=top;i++)
	{
		while((b[i+1]-b[i])*(b[q+1]-b[i])>(b[i+1]-b[i])*(b[q]-b[i]))
		  q=q%top+1;
		ans=max(ans,dis(b[q],b[i]));
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	Graham();
	printf("%d\n",Calc());
}

求两个凸多边形最近距离

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-10
using namespace std;
struct node{ double x,y; }a[10005],b[10005],t;
double ans; 
double dis(node a,node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Cross(node a,node b,node c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
double Dot(node a,node b,node c)
{
	return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);
}
bool cmp(node aa,node bb)
{
	double k=Cross(aa,bb,t);
	return (!k)?dis(aa,t)<dis(bb,t):k>0;
}
void Sort(node *a,int n)
{
	int k=1;
	for(int i=2;i<=n;i++) if((a[k].y>a[i].y)||(a[k].y==a[i].y&&a[k].x>a[i].x)) k=i;
	t=a[k];
	sort(a+1,a+n+1,cmp);
}
void Add(node x,node y,node z)
{
	if(Dot(z,y,x)/dis(x,z)/dis(x,y)<-eps) ans=min(ans,dis(x,z));
	else if(Dot(x,z,y)/dis(y,z)/dis(x,y)<-eps) ans=min(ans,dis(y,z));
	else ans=min(ans,fabs(Cross(z,y,x))/dis(x,y));
}
void Calc(node *a,node *b,int n,int m)
{
	int P=1,Q=1;
	for(int i=1;i<=n;i++)  if(a[i].y<a[P].y) P=i;
	for(int i=1;i<=m;i++)  if(b[i].y>b[Q].y) Q=i;
 	for(int i=1,t;i<=n;i++)
	{
		while(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<-eps) Q=Q%m+1;
		Add(a[P],a[P+1],b[Q]);
		if(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<eps) Add(a[P],a[P+1],b[Q+1]);
		P=P%n+1;
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)&&n)
	{
		ans=30000;
		for(int i=1;i<=n;i++)  scanf("%lf%lf",&a[i].x,&a[i].y); 
		for(int i=1;i<=m;i++)  scanf("%lf%lf",&b[i].x,&b[i].y);
		Sort(a,n);Sort(b,m);
		a[n+1]=a[1];b[m+1]=b[1];
		Calc(a,b,n,m);Calc(b,a,m,n);
		printf("%.6lf\n",ans);
	}
}

3.4 概率期望

3.5 矩阵

3.5.1 矩阵乘法

#include <cstring>
#include <cstdio>
struct Matrix{
	int m[11][11],W,H;
};
Matrix operator * (const Matrix a,const Matrix b) //默认a.W==b.H
{
	Matrix c;  
	c.H=a.H;c.W=b.W;
	memset(c.m,0,sizeof(c.m));
	for(int i=1;i<=c.H;i++)
	  for(int j=1;j<=c.W;j++)
	  	for(int k=1;k<=a.W;k++)
	      c.m[i][j]+=a.m[i][k]*b.m[k][j];
	return c;
}

3.5.2 高斯消元

#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-6
using namespace std;
int n,k;
double t,a[15][15];
int main()
{
	for(int i=1;i<=n;i++)
	{
		if(fabs(a[i][i])<eps) 
		{
			for(int j=i+1;j<=n;j++)
			  if(fabs(a[j][i])>=eps) {k=j;break;}
			swap(a[i],a[k]);
		}
		t=a[i][i];
		for(int j=1;j<=n+1;j++) a[i][j]/=t;
		for(int j=1;j<=n;j++)
		  if(j!=i)
		  {
		  	t=a[j][i];
		  	for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*t;
		  }
	}
	for(int i=1;i<=n;i++) printf("%.3lf ",a[i][n+1]);
}

#include <iostream>
#include <cstdio>
const int N=1001;
int n,m,line,row,a[N][N+1],sure[N];
int gcd(int x,int y)
{
	return !y?x:gcd(y,x%y);
}
int Guass()
{
	for(line=row=1;line<=n&&row<=m;line++,row++) //line->hang row->lie 
	{
		int t=line;while(t<=n&&!a[t][row]) t++;
		if(t>n) {line--;continue;}
		if(t!=line) std::swap(a[t],a[line]);
		for(int i=1;i<=n;i++)
			if(i!=line&&a[i][row])
			{
				int d=gcd(a[i][row],a[line][row]);
				int ta=a[line][row]/d,tb=a[i][row]/d;
				for(int j=1;j<=m+1;j++)
					a[i][j]=a[i][j]*ta-a[line][j]*tb;
			}
	}
	line--;row--;
	for(int i=line+1;i<=n;i++)
	  if(a[i][m+1]) return -1;
	if(line<m)
	{
		for(int i=1;i<=m;i++) sure[i]=-1;
		for(int i=line;i;i--)
		{
			int cnt=0,num;
			for(int j=1;j<=m;j++)
			  if(a[i][j]&&sure[j]==-1) cnt++,num=j;
			if(cnt==1) sure[num]=a[i][m+1];
		}
		return 1;
	} 
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m+1;j++)
	    scanf("%d",&a[i][j]);
	Guass();
}

3.5.2 MatrixTree定理

• 无向图
  邻接矩阵G：对于无向图的边(u,v)，G[u][v]++,G[v][u]++.
  度数矩阵D：对于无向图的边(u,v)，D[u][u]++,D[v][v]++.
  基尔霍夫矩阵：C=D-G.
  Matrix Tree定理：将图G的基尔霍夫矩阵去掉第i行和第i列，得到(n-1)*(n-1)的矩阵,对这个矩阵进行行列式的值求解，abs(det(A))即为图G的生成树个数。

• 有向图
  树形图：以i点为根节点的树形图有(n-1)条边，从i节点出发可以到达其他所有(n-1)个节点.
  邻接矩阵G：对于有向图的边(u,v)，G[u][v]++.
  度数（入度）矩阵D：对于有向图的边(u,v)，D[v][v]++.
  基尔霍夫矩阵：C=D-G.
  有向图Matrix Tree定理：将有向图G的基尔霍夫矩阵去掉第i行和第i列，得到(n-1)*(n-1)的矩阵，对这个矩阵进行行列式的值求解，abs(det(A))就是以i为根的树形图的个数。

3.6 博弈论

4 图论

4.1 二分图的性质

性质1：最小点覆盖数 = 最大匹配数
性质2：最小边覆盖数 = 最大独立集
性质3：最小点覆盖数 + 最大独立集 = 顶点数
性质4：最大团 = 补图的最大独立集

其中：
点覆盖：点集，满足每条边都被接触
边覆盖：边集，满足每个顶点都被接触
匹配：边集，满足任意两条边都没有公共顶点
独立集：点集，满足两两不相连
团：点集，满足两两相连（完全图）

4.2 Tarjan

#include <iostream>
#include <cstdio>
const int N=1e4+5;
const int M=1e5+5;
int n,m,dfsnum,tot,top,ecnt,st[N],dfn[N],low[N],pos[N],head[N],to[M],next[M];
bool vis[N];
void Addedge(int x,int y)
{
	to[++ecnt]=y;next[ecnt]=head[x];head[x]=ecnt;
}
void Tarjan(int x)
{
	dfn[x]=low[x]=++dfsnum;
	vis[x]=1;
	st[++top]=x;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(!dfn[y])
			Tarjan(y),low[x]=std::min(low[x],low[y]);
		else if(vis[y])
			low[x]=std::min(low[x],dfn[y]);
	if(dfn[x]==low[x])
	{
		tot++;
		for(int y=-1;y!=x;)
		{
			y=st[top--];
			pos[y]=tot;
			vis[y]=0;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),Addedge(x,y);
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
}

4.3 最短路

SPFA O(kE)

memset(ds,0x7f,sizeof(ds));
ds[S]=0; vis[S]=1; q.push(S);
while(!q.empty())
{
	int x=q.front(); q.pop(); vis[x]=0;
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i],c=cost[x][i];
		if(ds[y]>ds[x]+c)
		{
			ds[y]=ds[x]+c;
			if(!vis[y])
			{
				vis[y]=1; q.push(y);
			}
		}
	}
}

Dijkstra O(n*logn)

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=10005;
const int M=100005;
const int inf=0x7fffffff;
int st[N],next[2*M],ed[2*M],cost[2*M],tot,ds[N],n,m;
void add(int x,int y,int z)
{
	next[++tot]=st[x],st[x]=tot,ed[tot]=y,cost[tot]=z;
}
struct node{
	int x,d;
	node(int a,int b):x(a),d(b){}
	bool operator<(const node&t) const{return d>t.d;}
};
priority_queue<node> q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z); add(y,x,z);
	}
	int S=1,T=n;
	for(int i=1;i<=n;i++) ds[i]=inf;
	q.push(node(S,0));
	while(!q.empty()){
		node x=q.top(); q.pop();
		if(ds[x.x]<inf) continue;
		ds[x.x]=x.d;
		for(int now=st[x.x];now;now=next[now]) 
			q.push(node(ed[now],x.d+cost[now]));
	}
	printf("%d\n",ds[T]);
}

4.4 最小生成树

Kruskal O(E*logE)

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,x,y,z,f1,f2,tot,k,fa[1001];
struct node{
	int x,y,v;
}a[10001];
int cmp(const node &a,const node &b)
{
	return a.v<b.v;
}
int father(int x)
{
	return fa[x]==x?x:fa[x]=father(fa[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		x=a[i].x;y=a[i].y;z=a[i].v;
		f1=father(x);f2=father(y);
		if(f1==f2) continue;
		fa[f1]=f2;tot+=z;k++;
		if(k==n-1) break;
	}
	printf("%d",tot);
}

Prime

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,x,y,z,tot,ans,k,ds[1001],next[2001],st[1001],to[2001],cost[2001];
bool vis[1001];
void addedge(int x,int y,int z)
{
	next[++tot]=st[x];st[x]=tot;to[tot]=y;cost[tot]=z;
}
struct node
{
	int x,d;
	node(int a,int b):x(a),d(b) {}
	bool operator<(const node&t) const {return d>t.d;}
}; priority_queue<node>q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
	    addedge(x,y,z);addedge(y,x,z); 
	}
	memset(ds,0x7f,sizeof(ds));
	ds[1]=0;q.push(node(1,0));vis[0]=1;
	for(int i=1;i<=n;i++)
	{
		node a(0,0);
		while(vis[a.x]&&!q.empty())
          a=q.top(),q.pop();
		if(vis[a.x]) break;
		ans+=a.d;vis[a.x]=1;k++;
		for(int j=st[a.x];j;j=next[j])
		{
			y=to[j];z=cost[j];
			if(!vis[y]&&z<ds[y])
		      ds[y]=z,q.push(node(y,z));
		}  
	}
	if(k!=n) printf("-1");
	else printf("%d",ans);
}

4.5 LCA

注意dep[1]=1;

for(int i=1;i<=log(n)/log(2)+1;i++)
  for(int j=1;j<=n;j++)
    fa[j][i]=fa[fa[j][i-1]][i-1],
    //g[j][i]=max(g[j][i-1],g[fa[j][i-1]][i-1]);
int lca(int x,int y)
{
    //int ans=0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=log(n)/log(2);i>=0;i--)
      if(dep[fa[x][i]]>=dep[y]) 
        //ans=max(ans,g[x][i]),
        x=fa[x][i];
    if(x==y) return x;
    for(int i=log(n)/log(2);i>=0;i--)
      if(fa[x][i]!=fa[y][i])
        //ans=max(ans,g[x][i]),ans=max(ans,g[y][i]),
        x=fa[x][i],y=fa[y][i];
    //ans=max(ans,g[x][0]);ans=max(ans,g[y][0]);
    return fa[x][0];
}

4.6 匈牙利算法

int used[N];   //记录y中节点是否使用 0表示没有访问过，1为访问过
int linker[N];   //记录当前与y节点相连的x的节点  
int g[N][N];   //记录连接x和y的边，如果i和j之间有边则为1，否则为0
int vn,vm;     //二分图中x和y中点的数目  
bool dfs(int u)//从左边开始找增广路径
{
    for(int v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改
      if(g[u][v]&&!used[v])
      {
          used[v]=true;
          if(linker[v]==-1||dfs(linker[v]))
          {//找增广路，反向
              linker[v]=u;
              return true;
          }
      }
    return false;//这个不要忘了，经常忘记这句
}
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}

5 网络流

5.1 Dinic

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N=5005,M=10005;
int n,m,S,T,ans,ecnt=1,ds[N],head[N],to[M<<1],rest[M<<1],next[M<<1];
std::queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++ecnt]=y;rest[ecnt]=z;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
bool Bfs()
{
	memset(ds,0,sizeof(ds));
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&!ds[y])
		    ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
	  if(rest[e]&&ds[y]==ds[x]+1)
	  {
	  	b=Dfs(y,std::min(flow-a,rest[e]));
	  	rest[e]-=b;rest[e^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=1,x,y,z;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),Addedge(x,y,z);
	while(Bfs()) ans+=Dfs(S,0x7fffffff);
	printf("%d\n",ans);
}

5.2 ISAP

int source;         // 源点
int sink;           // 汇点
int p[max_nodes];   // 可增广路上的上一条弧的编号
int num[max_nodes]; // 和 t 的最短距离等于 i 的节点数量
int cur[max_nodes]; // 当前弧下标
int d[max_nodes];   // 残量网络中节点 i 到汇点 t 的最短距离
bool visited[max_nodes];
// 预处理, 反向 BFS 构造 d 数组
bool bfs()
{
    memset(visited, 0, sizeof(visited));
    queue<int> Q;
    Q.push(sink);
    visited[sink] = 1;
    d[sink] = 0;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) {
            Edge &e = edges[(*ix)^1];
            if (!visited[e.from] && e.capacity > e.flow) {
                visited[e.from] = true;
                d[e.from] = d[u] + 1;
                Q.push(e.from);
            }
        }
    }
    return visited[source];
}
// 增广
int augment()
{
    int u = sink, df = __inf;
    // 从汇点到源点通过 p 追踪增广路径, df 为一路上最小的残量
    while (u != source) {
        Edge &e = edges[p[u]];
        df = min(df, e.capacity - e.flow);
        u = edges[p[u]].from;
    }
    u = sink;
    // 从汇点到源点更新流量
    while (u != source) {
        edges[p[u]].flow += df;
        edges[p[u]^1].flow -= df;
        u = edges[p[u]].from;
    }
    return df;
}
int max_flow()
{
    int flow = 0;
    bfs();
    memset(num, 0, sizeof(num));
    for (int i = 0; i < num_nodes; i++) num[d[i]]++;
    int u = source;
    memset(cur, 0, sizeof(cur));
    while (d[source] < num_nodes) {
        if (u == sink) {
            flow += augment();
            u = source;
        }
        bool advanced = false;
        for (int i = cur[u]; i < G[u].size(); i++) { 
            Edge& e = edges[G[u][i]];
            if (e.capacity > e.flow && d[u] == d[e.to] + 1) {
                advanced = true;
                p[e.to] = G[u][i];
                cur[u] = i;
                u = e.to;
                break;
            }
        }
        if (!advanced) { // retreat
            int m = num_nodes - 1;
            for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix)
                if (edges[*ix].capacity > edges[*ix].flow)
                    m = min(m, d[edges[*ix].to]);
            if (--num[d[u]] == 0) break; // gap 优化
            num[d[u] = m+1]++;
            cur[u] = 0;
            if (u != source)
                u = edges[p[u]].from;
        }
    }
    return flow;
}

5.3 MCF

#include<cstdio>
#include<queue>
using namespace std;
const int inf=0x3fffffff;
const int N=100;
const int M=2000;
int n,m,S,T,ds[N],pre[N],maxflow,mincost;
int ecnt=1,st[N],to[M*2],rest[M*2],cost[M*2],next[M*2];
bool used[N];
queue<int> Q;
void Addedge(int x,int y,int r,int c)
{
	to[++ecnt]=y;rest[ecnt]=r;cost[ecnt]=c;next[ecnt]=st[x];st[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;cost[ecnt]=-c;next[ecnt]=st[y];st[y]=ecnt;
}
bool Spfa()
{
	for(int i=0;i<=T;i++) ds[i]=inf;
	Q.push(S);ds[S]=0;used[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();used[x]=0;
		for(int e=st[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&ds[y]>ds[x]+cost[e])
		  {
		  	ds[y]=ds[x]+cost[e];
		  	pre[y]=e;
		  	if(!used[y]) used[y]=1,Q.push(y); 
		  }
	}
	return ds[T]<inf;
}
void Update(int flow)
{
	for(int e=pre[T];e;e=pre[to[e^1]])
	  flow=min(flow,rest[e]);
	for(int e=pre[T];e;e=pre[to[e^1]])
	  rest[e]-=flow,rest[e^1]+=flow;
	maxflow+=flow;mincost+=flow*ds[T];
}
int main()
{
	scanf("%d%d",&n,&m);
	S=1;T=n;
	for(int i=1,u,v,r,c;i<=n;i++)
	  scanf("%d%d%d%d",&u,&v,&r,&c),Addedge(u,v,r,c);
	while(Spfa()) Update(inf);
	printf("Maxflow:%d\nMinflow:%d\n",maxflow,mincost);
}

5.4 上下界网络流

一、无源汇

1. 可行流

可以想到为了满足流量的下限 \(low\)，将边的流量设为 \(high-low\)。
但是求出这个图的最大流之后，加上 \(low\)，会使得某些点不满足流量平衡。
所以可以建立附加源和附加汇，来补充和吸收这些流量。

法一：

由于下届是一条弧上的流必需要满足的确定值。下面引出必要弧的概念：必要弧是一定流要满的弧。必要弧的构造，讲容量下界的限制分离开了，从而构造了一个没有下界的网络\(G'\)：
1.将原弧\((u,v)\)分离出一条必要弧：\(c'(u,v)_ {nes}=b(u,v)\).（红色表示）
2.原弧：\(c'(u,v)=c(u,v)-b(u,v)\).
由于必要弧的有一定要满的限制，将必要弧“拉”出来集中考虑：
添加附加源\(x\)，附加汇\(y\)。想象一条不限上届的\((y,x)\)，有必要弧将它们“串”起来，即对于有向必要弧\((u,v)\)，添加\((u,y),(x,v)\)，容量为必要弧容量。这样就建立了一个等价的网络。
一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉\((y,x)\)后，附加源\(x\)到汇\(y\)的最大流，能使得\(x\)的出弧或者\(y\)的入弧都满，充要于原图有可行流。
即对于一条边 \((u,v)\) ，在图中建三条边 \((u,v,high-low) , (S,v,low) , (u,T,low)\)

法二：
发现上图中存在许多流量可以直接从 \(S\) 经过点 \(x\) 到 \(T\) ，这样的流量对答案没有贡献
所以考虑 \(du[i]\) 表示点 \(i\) 的入度-出度，则如果 \(du[i] > 0\)，建边\((S,i,du[i])\)；否则建边\((i,T,-du[i])\)。这样就省去了不少空间。

二、有源汇

1. 可行流
   从 \(T\) 向 \(S\) 连一条 \([0,inf]\) 的边，有源汇就变成了无源汇，就和上面一样了

2. 最大流

法一：
二分最大流量，判断是否可行
即 \(T\)->\(S\) 的边的流量为 \([x,inf]\)
1 . \(x>ans\) 即 \(min(T->S) > max(S->T)\) ,会使求新网络的无源汇可行流无解的（S,T流量怎样都不能平衡）
2 . \(x<=ans\) 会有解.

法二：
1 . 连上 \(T\)->\(S\) 流量为 \(inf\) 的边，求一次附加源到附加汇的最大流，若不满流则无解
2 . 在残量网络上求一次 \(s\) 到 \(t\) 的最大流
3 . 答案就是第二次求出的最大流（因为第一次求出的最大流是 \(T\)->\(S\) 的流量，而这个流量在他的反向边 \(s\)->\(t\) 中出现，所以不需要另外加上）

第一次求出的最大流是为了满足 \(low\) 尽可能流满，然而此时 \(s\)->\(t\) 上可能还有可行的流，我们在残量网络上继续来求最大流，可以使得最后求出的流既满足 \(≥low\) 的限制，且最大。

3. 最小流

法一：
二分最小流量，判断是否可行
即 \(T\)->\(S\) 的边的流量为 \([0,x]\)

法二：
1 . 先不连 \(T\)->\(S\) 流量为 \(inf\) 的边，求一次附加源到附加汇的最大流
2 . 再连上 \(T\)->\(S\) 流量为 \(inf\) 的边，在残量网络上求一次 \(s\) 到 \(t\) 的最大流
3 . 若最后满流，则答案为 \(T\)->\(S\) 的反向边的流量

因为第一遍做的时候并无这条边，所以 \(s\)->\(t\)的流量在第一遍做的时候都已经尽力往其他边流了.
于是加上 \(T\)->\(S\) 这条边后，都是些剩余的流不到其他边的流量. 从而达到尽可能减少 \(T\)->\(S\) 这边上的流量的效果，即减小了最终答案.

6 其他

6.1 读入优化

int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

#define isNum(c) ('0' <= (c) && (c) <= '9')
char buff[15000000],*pb=buff;
char mvpb(){
	char ret=*(pb++);
	if(pb==buff+sizeof(buff)){
		fread(buff,sizeof(char),sizeof(buff),stdin);
		pb=buff;
	}
	return ret;
}
int readInt(){
	int ret=0;
	while(!isNum(*pb)){
		mvpb();
	}
	while(isNum(*pb)) ret=(ret<<1)+(ret<<3)+(mvpb())-'0';
	return ret;
}
int main(){
	fread(buff,sizeof(char),sizeof(buff),stdin);
}

6.2 STL

6.2.1 set

set:不可重复 multiset:可重复

基本操作：
1. begin() : 返回第一个元素的位置
2. end() : 返回最后一个元素的位置
3. clear() : 删除set容器中的所有的元素
4. empty() : 判断set容器是否为空
5. size() : 返回当前set容器中的元素个数
6. count() : 某个键值出现的次数
7. find() : 返回给定值值得定位器，如果没找到则返回end()
8. 遍历：for(set<int>::iterator iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);

插入&删除：
1. insert(key_value) : 将key_value插入到set中 ，返回值是pair<set<int>::iterator, bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。
2. inset(first,second) : 将定位器first到second之间的元素插入到set中，返回值是void.
1. erase(iterator) : 删除定位器iterator指向的值
2. erase(first,second) : 删除定位器first和second之间的值
3. erase(key_value) : 删除键值key_value的值

前后：
1. upper_bound(key_value) : 大于key_value的定位器
2. lower_bound(key_value) : 大于等于key_value的定位器
3. --upper_bound(key_value) : 小于等于key_value的定位器
4. --lower_bound(key_value) : 小于key_value的定位器

6.2.2 vector

在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.

1. 创建vector对象 : vector<int> vec;
2. 尾部插入数字 : vec.push_back(a);
3. 使用下标访问元素 : cout<<vec[i]<<endl;记住下标是从0开始的。
4. 使用迭代器访问元素 : for(iter=vec.begin();iter!=vec.end();it++) printf("%d ",*iter);
5. 插入元素 : vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a
6. 删除元素 : vec.erase(vec.begin()+i);删除第i+1个元素
7. 删除区间 : vec.erase(vec.begin()+i,vec.begin()+j);删除区间[i,j-1]
8. 大小 : vec.size();
9. 清空 : vec.clear();
10. 使用reverse将元素翻转 : reverse(vec.begin(),vec.end());
11. 使用sort排序 : sort(vec.begin(),vec.end());

6.3 背包

• 01背包

  for(int i=1;i<=n;i++)
    for(int v=0;v<=m;v++)
    {
    	if(v-w[i]>=0) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
    	else f[i][v]=f[i-1][v];
    }
    
  for(int i=1;i<=n;i++)
    for(int v=m;v>=w[i];v--)
      f[v]=max(f[v],f[v-w[i]]+c[i]);

• 完全背包 优化：拆成\(w[i]*2^k\) , \(c[i]*2^k\) 的若干件（其中\(w[i]*2^k<V\)）

  for(int i=1;i<=n;i++)
    for(int v=0;v<=m;v++)
    {
    	if(v-w[i]>=0) f[i][v]=max(f[i-1][v],f[i][v-w[i]]+c[i]);
    	else f[i][v]=f[i-1][v];
    } 
    
  for(int i=1;i<=n;i++)
    for(int v=w[i];v<=m;v++)
      f[v]=max(f[v],f[v-w[i]]+c[i]);

• 多重背包
  优化：拆成 \(1, 2, 4, \dots, 2^{(k-1)} , n[i]-2^k+1\) （其中 \(k\) 为满足 \(n[i]-x^k+1>0\) 的最大整数)

  for(int i=1;i<=n;i++)
    for(int v=0;v<=m;v++)
      for(int k=0;k<=num[i];k++)
      {
      	f[i][v]=max(f[i][v],f[i-1][v]);
    	    if(v-k*w[i]>=0) f[i][v]=max(f[i][v],f[i-1][v-k*w[i]]+k*c[i]);
      }
      
  for(int i=1;i<=n;i++)
    for(int v=m;v>=0;v--)
      for(int k=0;k<=num[i];k++)
  	{
  		if(v-k*w[i]<0) break;
  		f[v]=max(f[v],f[v-k*w[i]]+k*c[i]);
  	}