常用易错代码块总结+详解

# 【永远置顶】万能程序模板
```cpp
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(0),cout.tie(0);
	
	return 0;
}
/*
---INFORMATIONS---
TIME:<DATETIME>
PROBLEM:%REPL_BEGIN%P%REPL_END%
CODE BY __CrossBow_EXE__ Luogu uid967841
*/
```

# 数据结构模板
## 大根堆，一条大根堆

```cpp
int heap[10005],num=0;//大根堆 
void in(int x){
	heap[++num]=x;
	int fa;
	int son=num;
	while(son/2){
		fa=son/2;
		if(heap[son]>heap[fa]) swap(heap[son],heap[fa]);
		else break;
		son=fa;
	}
}

int out(){
	int res=heap[1];
	heap[1]=heap[num--];
	int fa=1,son;
	while(fa*2<=num){
		son=fa*2;
		if(son+1<=num&&heap[son]<heap[son+1]) son++;
		if(heap[son]>heap[fa]) swap(heap[son],heap[fa]);
		else break;
		fa=son;
	}
	return res;
}
```

## 小根堆

```cpp
int heap[10005],num=0;//小根堆 
void in(int x){
	heap[++num]=x;
	int fa;
	int son=num;
	while(son/2){
		fa=son/2;
		if(heap[son]<heap[fa]) swap(heap[son],heap[fa]);
		else break;
		son=fa;
	}
}

int out(){
	int res=heap[1];
	heap[1]=heap[num--];
	int fa=1,son;
	while(fa*2<=num){
		son=fa*2;
		if(son+1<=num&&heap[son]>heap[son+1]) son++;
		if(heap[son]<heap[fa]) swap(heap[son],heap[fa]);
		else break;
		fa=son;
	}
	return res;
}
```
## 单调栈

```cpp
for(int i=1;i<=n;i++){
  while(!st.empty()&&a[st.top()]<a[i]) num[st.top()]=i,st.pop();
  st.push(i);
}
```

## 单调队列（滑动窗口）

```cpp
head=0,tail=-1;
for(int i=1;i<=n;i++){
	while(head<=tail&&a[q[tail]]>=a[i]) tail--;//窗口最小值
	q[++tail]=i;
	while(q[head]<i-k+1) head++;
	if(i>=k) cout<<a[q[head]]<<' ';
}
cout<<endl;
```

## ST表
输入

```cpp
for(int i=1;i<=n;i++){
	cin>>a[i][0];
}
```

预处理

```cpp
for(int j=1;j<20;j++){
	for(int i=1;i<=n;i++){
		a[i][j]=max(a[i][j-1],a[min(i+(1<<j-1),n)][j-1]);
	}
}
```

查询

```cpp
while(m--){
	cin>>l>>r;
	int k=log2(r-l+1);
	cout<<max(a[l][k],a[r-(1<<k)+1][k])<<endl;
}
```

## 真神线段树
### 单点修改、求区间和

[原题](https://www.luogu.com.cn/problem/P3374)

```cpp
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1000005;
int n,m,op,x,y;
int a[N];
struct node{
	int l,r,sum;//左右儿子 区间和 
}tr[N<<2];//共4*n个线段树节点 
void pushup(int u){//和向上传递 
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	//和=左边和+右边和 
}
void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r;
	if(l==r){//如果到了叶子区间 
		tr[u].sum=a[l];//和直接就是a[l] 
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);//建左边 
	build(u<<1|1,mid+1,r);//建右边
	pushup(u);//传递上去 
}
void modify(int u,int x,int k){
	if(tr[u].l==tr[u].r){//是叶子节点 
		tr[u].sum+=k;//直接修改就行 
		return;
	}
	//tr[u].l - tr[u].r
	int mid=(tr[u].l+tr[u].r)>>1;
	//tr[u].l - mid,mid+1 - tr[u].r
	if(x<=mid) modify(u<<1,x,k);//改左边 
	else modify(u<<1|1,x,k);//改右边 
	pushup(u);
}
int ask(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;//包含在区间内，直接输出和
	int mid=(tr[u].l+tr[u].r)>>1,sum=0;
	if(mid>=l) sum+=ask(u<<1,l,r);//加左边 
	if(mid<r) sum+=ask(u<<1|1,l,r);//加右边 
	return sum;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);//从1建到n 
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			modify(1,x,y);//a[x]+=y 
		}else{
			cin>>x>>y;
			cout<<ask(1,x,y)<<endl;
		}
	}
	return 0;
}
```

### 区间修改、求区间和

[原题](https://www.luogu.com.cn/problem/P3372)

```cpp
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define int long long
using namespace std;
const int N=100005;
int a[N];
int n,m,op,x,y,k;
struct node{
	int l,r,sum,lazy;
}tr[N<<2];
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
	if(tr[u].lazy){//有懒标记才pushdown 
		tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy;//区间和增加（区间元素个数）个懒标记 
		tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy;
		tr[u<<1].lazy+=tr[u].lazy;//把懒标记传递给左右孩子 
		tr[u<<1|1].lazy+=tr[u].lazy;
		tr[u].lazy=0;//清空懒标记 
	}
}
void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r;
	if(l==r){
		tr[u].sum=a[l];
		tr[u].lazy=0;//懒标记初始化 
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int l,int r,int val){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].sum+=val*(tr[u].r-tr[u].l+1);//需要加很多个val 
		tr[u].lazy+=val;//懒标记一下，标记加上过val
		return; 
	}
	pushdown(u);//懒标记下传
	int mid=(tr[u].l+tr[u].r)>>1;
	if(mid>=l) modify(u<<1,l,r,val);
	if(mid<r) modify(u<<1|1,l,r,val);
	pushup(u); 
}
int ask(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].sum;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1,sum=0;
	if(mid>=l) sum+=ask(u<<1,l,r);
	if(mid<r) sum+=ask(u<<1|1,l,r);
	return sum;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modify(1,x,y,k);
		}else{
			cin>>x>>y;
			cout<<ask(1,x,y)<<endl;
		}
	} 
	return 0;
}
```

## 树状数组
### 单点修改区间查询

```cpp
void add(int x,int k){//将a[x]加上k 
	for(;x<N;x+=x&-x){
		tr[x]+=k;
	}
}
int ask(int x){//求1-x的和 
	int ans=0;
	for(;x;x-=x&-x){
		ans+=tr[x];
	}
	return ans;
}
```

### 区间修改单点查询

不使用树状数组维护 $a_i$，而是维护差分数组 $cf_i=a_i-a_{i-1}$。

修改：

```cpp
cin>>x>>y>>k;
add(x,k);
add(y+1,-k);
```

查询：

```cpp
cin>>x;
cout<<ask(x)<<endl;
```

### 区间修改区间查询

开两个树状数组：`int tr[N][2];`

修改、查询：

```cpp
void add(int x,int k,int op){
	for(;x<N;x+=x&-x){
		tr[x][op]+=k;
	}
}
int ask(int x,int op){
	int ans=0;
	for(;x;x-=x&-x){
		ans+=tr[x][op];
	}
	return ans;
}
```

初始化：

```cpp
for(int i=1;i<=n;i++){
  cin>>a[i];
  add(i,a[i]-a[i-1],0);
  add(i,i*(a[i]-a[i-1]),1); 
}
```

查询：

```cpp
for(int i=1,op,x,y,k;i<=m;i++){
  cin>>op>>x>>y;
  if(op==1){
    cin>>k;
    add(x,k,0);
    add(y+1,-k,0);
    add(x,x*k,1);
    add(y+1,-(y+1)*k,1);
  }else{
    cout<<solve(y)-solve(x-1)<<endl;
  }
}
```

## 并查集
### 【优化】路径压缩

```cpp
int find(int x){//查
	if(f[x]==x) return x;
	else return f[x]=find(f[x]); 
}
void merge(int x,int y){//并 
	int a=find(x),b=find(y);
	if(a!=b) f[a]=b;
}
```

### 【优化】启发式合并

```cpp
int f[N],siz[N];
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	int a=find(x),b=find(y);
//	if(a!=b) f[a]=b;
	if(a==b) return;
	if(siz[a]>siz[b]){
		f[b]=a;
		siz[a]+=siz[b];
	}else{
		f[a]=b;
		siz[b]+=siz[a];
	}
}
//主函数中for(int i=1;i<=N;i++) siz[i]=1;
```

### 【优化】随机合并

```cpp
//#include<cstdlib>

int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	int a=find(x),b=find(y);
	if(a==b) return;
	if(rand()&1) /*rand()%2==0*/f[a]=b;
	else f[b]=a;
}
```

## 平衡树

### Splay

```cpp
int getwh(int x){return ch[f[x]][1]==x;}
void pushup(int x){
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+cnt[x];
}
void rotate(int x){//转 
	int y=f[x],z=f[y],k=getwh(x);//y是爸爸，z是爷爷 
	f[x]=z;
	ch[z][getwh(y)]=x;
	f[ch[x][k^1]]=y;
	ch[y][k]=ch[x][k^1];
	f[y]=x;
	ch[x][k^1]=y;
	pushup(y);
	pushup(x);
}
void splay(int x,int tar){//把x旋转到tar的儿子 
	if(x==-1) return;
	while(f[x]!=tar){
		int y=f[x],z=f[y];
		if(z!=tar){
			if(getwh(y)==getwh(x)) rotate(y);//共线 
			else rotate(x);
		}
		rotate(x);
	}
	if(tar==0) root=x;
}
void insert(int v){//插入v 
	int x=root,y=0;
	while(x&&v!=a[x]){//看看v要插入到哪里 
		y=x;
		x=ch[x][v>a[x]];
	}
	if(x) cnt[x]++,sum[x]++;//有v这个节点 
	else{//没有 
		x=++tot;
		if(y) ch[y][v>a[y]]=x;//有父亲
		f[x]=y;
		sum[x]=cnt[x]=1;//初始化子树大小、值的个数 
		a[x]=v; 
	}
	splay(x,0);
}
void find(int v){//找到v并旋转到根节点 
	int x=root;
	if(!x) return;//根节点
	while(ch[x][v>a[x]]&&v!=a[x]) x=ch[x][v>a[x]];//有儿子就一直往下找
	splay(x,0);//转到根 
}
int nxt(int v,int f){
	find(v);//旋到根 
	int x=root;
	if(a[x]>v&&f==1) return x;//后继
	if(a[x]<v&&f==0) return x;//前驱
	x=ch[x][f];//走一步 
	while(ch[x][f^1]) x=ch[x][f^1];//一直往下，反方向走 
	return x; 
}
void erase(int v){
	int pre=nxt(v,0),next=nxt(v,1);//找前驱和后继
	splay(pre,0);splay(next,pre);
	int x=ch[next][0];//v一定到了next左边
	if(cnt[x]>1){//v这个值不止一个 
		cnt[x]--;
		pushup(x);
		splay(x,0);
	}else{
		ch[next][0]=0;//删掉后继的左儿子 
		f[x]=0;
	}
}
int getrank(int v){//v的排名，有多少个数小于v 
	int x=root,rank=0;
	while(x){
		if(a[x]>v) x=ch[x][0];//大了，往左走
		else if(a[x]==v){//找到了
			rank+=sum[ch[x][0]]; 
			tag=x;
			return rank;
		} 
		else{
			rank+=sum[ch[x][0]]+cnt[x];
			x=ch[x][1];//小了，往右走 
		}
	}
	return rank;
}
int kth(int k){
	int x=root;
	while(1){
		if(sum[ch[x][0]]>=k) x=ch[x][0];//左边有至少k个，一定在左边
		else if(sum[ch[x][0]]+cnt[x]>=k){//左边不够，加上自己够了，一定是自己
			tag=x;
			return a[x];
		} 
		else{//在右边，往右走 
			k-=sum[ch[x][0]]+cnt[x];
			x=ch[x][1]; 
		} 
	}
}
```

### FHQ-Treap

```cpp
mt19937 rd(time(0));
struct node{
	int l,r;
	int val,key;//key随机分配 
	int sum;
}tr[N];
void pushup(int u){
	tr[u].sum=tr[ls].sum+tr[rs].sum+1;
}
void split(int u,int val,int &x,int &y){//分裂 
	if(!u){
		x=y=0;//到了底部
		return;
	}
	if(tr[u].val<=val){//值小了 
		x=u;
		split(rs,val,rs,y);//往右分裂 
	}else{//值大了 
		y=u;
		split(ls,val,x,ls);//往左分裂 
	}
	pushup(u);
}
int merge(int x,int y){//合并 
	if(!x||!y) return x+y;//一上一下，直接合并 
	if(tr[x].key>tr[y].key){//x大，y当x儿子 
		tr[x].r=merge(tr[x].r,y);
		pushup(x);
		return x;
	}else{//y大，x当y儿子 
		tr[y].l=merge(x,tr[y].l);
		pushup(y);
		return y;
	}
}
int new_node(int val){
	tr[++cnt]=(node){NULL,NULL,val,rd(),1};//无左右儿子，key随机生成 
	return cnt;
}
void insert(int val){
	split(root,val,x,y);//从val开始分裂
	root=merge(merge(x,new_node(val)),y);//合并两次 
}
void erase(int val){
	split(root,val,x,z);//x<=val  z>val
	split(x,val-1,x,y);//x<val  y==val
	y=merge(tr[y].l,tr[y].r);
	root=merge(merge(x,y),z);
}
int getrank(int val){
	x=root;
	int rank=0;
	while(x){
		if(tr[x].val<val) rank+=tr[tr[x].l].sum+1,x=tr[x].r;//往右 
		else x=tr[x].l;//往左 
	}
	return rank;
}
int kth(int k){
	x=root;
	while(x){
		if(tr[tr[x].l].sum>=k) x=tr[x].l;//左子树够了，往左跳
		else if(tr[tr[x].l].sum+1>=k) return tr[x].val;//正好是自己
		else{//左边不够 
			k-=tr[tr[x].l].sum+1;
			x=tr[x].r;//往右跳 
		} 
	}
}
int pre(int val){
	split(root,val-1,x,y);//往左跳一下 
	int u=x;
	while(tr[u].r) u=tr[u].r;//一直往右跳 
	merge(x,y);
	return tr[u].val;
}
int nxt(int val){
	split(root,val,x,y);//往左跳一下 
	int u=y;
	while(tr[u].l) u=tr[u].l;//一直往右跳 
	merge(x,y);
	return tr[u].val;
}
```

### 文艺平衡树

```cpp
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define l(x) (tr[x].l)
#define r(x) (tr[x].r)
#define f(x) (tr[x].f)
#define val(x) (tr[x].val)
#define sum(x) (tr[x].sum)
#define cnt(x) (tr[x].cnt)
#define lazy(x) (tr[x].lazy)
using namespace std;
int n,m;
const int N=100005;
struct node{
	int l,r,f;
	int val;
	int sum;
	int lazy;//懒标记 
}tr[N];
int root,cnt=0;
void pushup(int u){
	sum(u)=sum(l(u))+sum(r(u))+1;
}
void pushdown(int u){//旋转子树 
	if(lazy(u)){
		swap(l(u),r(u));
		lazy(l(u))^=1;
		lazy(r(u))^=1;
		lazy(u)=0;
	}
}
int getwh(int x){
	return r(f(x))==x;
}
void rotate(int x){
	int y=f(x),z=f(y),k=getwh(x);
	f(x)=z;
	if(getwh(y)) r(z)=x;
	else l(z)=x;
	if(k){
		f(l(x))=y;
		r(y)=l(x);
		f(y)=x;
		l(x)=y;
	}else{
		f(r(x))=y;
		l(y)=r(x);
		f(y)=x;
		r(x)=y;
	}
	pushup(y);
	pushup(x);
}
void splay(int x,int tar){
	while(f(x)!=tar){
		int y=f(x),z=f(y);
		if(z!=tar){
			if(getwh(y)==getwh(x)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(!tar) root=x;
}
int build(int l,int r,int f){//建树 
	if(l>r) return 0;
	int mid=(l+r)>>1,val=mid-1,tmp=++cnt;
	if(val==0) val=-2e9;
	else if(val==n+1) val=2e9;
	//建左右 
	tr[tmp]=(node){build(l,mid-1,tmp),build(mid+1,r,tmp),f,val,0,0};
	pushup(tmp);
	return tmp;
}
int kth(int k){//第几大，和之前没有区别 
	int x=root;
	while(x){
		pushdown(x);
		if(sum(l(x))>=k) x=l(x);
		else if(sum(l(x))+1>=k) return x;
		else{
			k-=sum(l(x))+1;
			x=r(x);
		}
	}
}
void print(int x){
	pushdown(x);
	if(l(x)) print(l(x));
	if(abs(val(x))!=2e9) cout<<val(x)<<' ';
	if(r(x)) print(r(x));
}
signed main(int argc,char *argv[]){
	ios::sync_with_stdio(NULL);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	root=build(1,n+2,0);
	for(int i=1,l,r,pre,nxt;i<=m;i++){
		cin>>l>>r;
		l++,r++;
		pre=kth(l-1),nxt=kth(r+1);
		splay(pre,0);
		splay(nxt,pre);
		lazy(l(r(root)))^=1;
	}
	print(root);
	return 0;
}
```

# 二分
## 二分答案万能模板

```cpp
bool check(int x){
	//TODO
}
int find(){
	int l=1,r=1e9,opt=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(opt==mid) break;
		opt=mid;
		if(check(mid)) r=mid;
		else l=mid;
	}
	if(check(min(l,r))) return min(l,r);
	else return max(l,r);
}
```

## 二分，但是实数

```cpp
const double eps=1e-6;//eps，误差值
while(r-l>eps){
	double mid=(l+r)/2;
	if(check(mid)) r=mid;
	else l=mid; 
} 
```

# 离散化

创建离散化 `vector`

```
vector<int> num;
```

求 $a_i$ 离散化后的值

```
int get(int x){
	return lower_bound(num.begin(),num.end(),x)-num.begin();
}
```

离散化

```
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
```

# 数学 & 数论
## 中缀表达式转表达式树

```cpp
long long dfs(int l,int r){
	int x=0,y=0,z=0;
	for(int i=l;i<=r;i++){
		if(a[i]=='(') x++;
		else if(a[i]==')') x--;
		else{
			if(x==0&&(a[i]<'0'||a[i]>'9')){
				if(a[i]=='*'||a[i]=='/') y=i;
				else z=i;
			}
		}
	}
	if(z){
		tree[z].l=dfs(l,z-1);
		tree[z].r=dfs(z+1,r);
		return z;
	}
	if(y){
		tree[y].l=dfs(l,y-1);
		tree[y].r=dfs(y+1,r);
		return y;
	}
	if(a[l]=='('&&a[r]==')') return dfs(l+1,r-1); 
	int k=0;
	for(int i=l;i<=r;i++){
		k=k*10+a[i]-'0';
	}
	tree[l].val=k;
	return l;
}

void pre(int x){//遍历
	if(tree[x].l) pre(tree[x].l);
	if(tree[x].r) pre(tree[x].r);
	c[++cnt]=x;
}
```

## gcd

```cpp
int gcd(int x,int y){
	if(y==0) return x;
	else return gcd(y,x%y);
}
```

## exgcd

```cpp
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
```

## 快速幂
### 正常版
```cpp
ll qpow(ll a,ll b,ll m){
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%m;//b%2==1
		a=a*a%m;
		b>>=1;//b/=2
	} 
	return ans;
}
```

### 压行版

```cpp
ll Pow(ll a,ll b,ll mod){
	ll ans=1;
	for(;b;a=a*a%mod,b>>=1){
		if(b&1) ans=ans*a%mod;
	}
	return ans;
}
```

## 素数筛法
### 正常筛
```cpp
bool prime(int x){
	if(x==0||x==1) return 0;
	if(x==2) return 1;
	for(int i=2;i*i<=x;i++){
		if(x%i==0) return 0;
	}
	return 1;
}
```
### 埃氏筛法
```cpp
void get_all_prime() {
	int cnt=0;
	prime[0]=1;
	prime[1]=1;
	for(int i=2; i<=40000; i++) {
		if(!prime[i]) {
			for(int j=2*i; j<=40000; j+=i) {
				prime[j]=0;
			}
		}
	}
}
```

### 欧拉筛 & 线性筛

```cpp
for(int i=2;i<=n;i++){
  if(!vis[i]) p.push_back(i);//如果是质数，就把它放进质数数组里 
  for(int j=0;j<p.size();j++){//遍历所有质数 
    if(i*p[j]>n) break;//边界情况 
    vis[i*p[j]]=1;//标记合数 
    if(i%p[j]==0) break;//能整除就退出，线性筛特点 
  }
}
```

## 逆元
给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

$a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

### 费马小定理
条件：$p$ 为质数。
```
Pow(n,p-2,p);//快速幂
```

### 扩展欧几里得
条件：无。【万能钥匙】

```cpp
exgcd(n,p,x,y);//扩展欧几里得模板
//答案：(x%p+p)%p
```

### 递推求逆元

```cpp
inv[1]=1;
for(ll i=2;i<=n;i++){
    inv[i]=(p-p/i)*inv[p%i]%p;
}
```

## 卢卡斯定理

```cpp
int Lucas(int n,int m){
	if(m==0) return 1;
	else return (Lucas(n/p,m/p)%p*C(n%p,m%p)%p)%p;
}
```

# 加快程序运行速度程序
## 快读&写
### 快读
```cpp
inline int read() {
	int x=0,f=1;
	char c=getchar();//读入第一个字符
	while(c<'0'||c>'9') {//如果这个字符不是数字
		if(c=='-')f=-1;//那么只能是减号，也就是负数标记
		c=getchar();//继续读入
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+c-48;//将字符转换为数字
		c=getchar();//继续读入
	}
	return x*f;//返回这个数字
}
```
### 快写
```cpp
void write(int x) {
	if (x < 0) {
		putchar('-');//如果这个数小于0，说明它是负数，先输出负数标记
		x = -x;//将这个数变成负数的它
	}
	if (x > 9) {
		write(x / 10);//递归式
	}
	putchar(x % 10 + '0');//输出数字
	return ;
}
```
## tie(0)
```cpp
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
```

## 超级快读

<https://www.luogu.me/paste/ilt13pl4>

```cpp
namespace Fast_I{
	char *_Buf,*_Start_ptr,*_End_ptr;
	streambuf *inbuf;
	unsigned int Size;
	bool _Ok;
	struct Fast_Istream{
		operator bool(){return _Ok;}
		Fast_Istream(streambuf *in,unsigned int Sz){
			_Ok=1;
			Fast_I::Size=Sz;
			inbuf=in;
			_Start_ptr=_End_ptr=_Buf=new char[Sz];
		}
		Fast_Istream(const char *in,unsigned int Sz){
			_Ok=1;
			Fast_I::Size=Sz;
			rdbuf(in);
			_Start_ptr=_End_ptr=_Buf=new char[Sz];
		}
		Fast_Istream(unsigned int Sz){
			_Ok=1;
			Fast_I::Size=Sz;
			_Start_ptr=_End_ptr=_Buf=new char[Sz];
		}
		void rdbuf(const char *File){
			static ifstream __In__(File);
			rdbuf(__In__.rdbuf());
		}
		void Get_Char(char &_Val){
			if(_Start_ptr==_End_ptr){
				_Start_ptr=_Buf;
				_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);
			}
			if(_Start_ptr==_End_ptr){
				_Val=-1;
				_Ok=0;
			}else _Val=*_Start_ptr++;
		}
		Fast_Istream &operator>>(char &_Val){
			if(_Ok){
				Get_Char(_Val);
				while(_Val==32||_Val==10||_Val==13||_Val==8||_Val==9||_Val==7||_Val==12||_Val==11) Get_Char(_Val);
			}
			return *this;
		}
		Fast_Istream &operator>>(char *_Val){
			if(_Ok){
				Get_Char(*_Val);
				while(*_Val==32||*_Val==10||*_Val==13||*_Val==8||*_Val==9||*_Val==7||*_Val==12||*_Val==11) Get_Char(*_Val);
				while(*_Val!=32&&*_Val!=10&&*_Val&&*_Val!=-1&&*_Val!=9 &&*_Val!=11&&*_Val!=12&&~*_Val) Get_Char(*++_Val);
				*_Val=0;
				--_Start_ptr;
			}
			return *this;
		}
		Fast_Istream &operator>>(string &_Val){
			if(_Ok){
				char c;
				Get_Char(c);
				while(c==32||c==10||c==13||c==8||c==9||c==7||c==12||c==11) Get_Char(c);
				for(_Val.clear();c!=32&&c!=10&&c&&c!=-1&&c!=9&&c!=11&&c!=12&&~c;Get_Char(c)) _Val.push_back(c);
				--_Start_ptr;
			}
			return *this;
		}
		template <typename Typex>
		void Get_Int(Typex &_Val){
			if(_Ok){
				char ch;
				bool _F=0;
				for(Get_Char(ch);(ch<48||ch>57)&&~ch;Get_Char(ch)) _F=ch==45;
				for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)) _Val=_Val*10+(ch^48);
				if(_F) _Val=~_Val+1;
				--_Start_ptr;
			}
		}
		template <typename Typex>
		void Get_Unsigned(Typex &_Val){
			if(_Ok){
				char ch;
				Get_Char(ch);
				while((ch<48||ch>57)&&~ch) Get_Char(ch);
				for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)) _Val=_Val*10+(ch^48);
				--_Start_ptr;
			}
		}
		template <typename Typex>
		void Get_Double(Typex &_Val){
			if(_Ok){
				char ch;
				bool _F=0;
				for(Get_Char(ch);(ch<48||ch>57)&&~ch;Get_Char(ch)) _F=ch==45;
				for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)) _Val=_Val*10+(ch^48);
				if(ch==46){
					unsigned long long _Pow=1;
					for(Get_Char(ch);ch>47&&ch<58&&~ch;Get_Char(ch)) _Val+=Typex((ch^48)*1.0/(_Pow*=10));
				}
				if(_F) _Val=-_Val;
				--_Start_ptr;
			}
		}
		Fast_Istream &operator>>(bool &_Val){
			if(_Ok){
				char ch;
				Get_Char(ch);
				while(ch==32||ch==10||ch==13||ch==8||ch==9||ch==7||ch==12||ch==11) Get_Char(ch);
				while(ch!=32&&ch!=10&&ch&&~ch&&ch!=9&&ch!=11&&ch!=12&&~ch){
					_Val|=ch!=48;
					Get_Char(ch);
				}
				--_Start_ptr;
			}
			return *this;
		}
		Fast_Istream &operator>>(short &_Val){
			Get_Int(_Val);
			return *this;
		}
		Fast_Istream &operator>>(int &_Val){
			Get_Int(_Val);
			return *this;
		}
		Fast_Istream &operator>>(long &_Val){
			Get_Int(_Val);
			return *this;
		}
		Fast_Istream &operator>>(long long &_Val){
			Get_Int(_Val);
			return *this;
		}
		Fast_Istream &operator>>(unsigned short &_Val){
			Get_Unsigned(_Val);
			return *this;
		}
		Fast_Istream &operator>>(unsigned int &_Val){
			Get_Unsigned(_Val);
			return *this;
		}
		Fast_Istream &operator>>(unsigned long &_Val){
			Get_Unsigned(_Val);
			return *this;
		}
		Fast_Istream &operator>>(unsigned long long &_Val){
			Get_Unsigned(_Val);
			return *this;
		}
		Fast_Istream &operator>>(float &_Val){
			Get_Double(_Val);
			return *this;
		}
		Fast_Istream &operator>>(double &_Val){
			Get_Double(_Val);
			return *this;
		}
		Fast_Istream &operator>>(long double &_Val){
			Get_Double(_Val);
			return *this;
		}
		template <typename Typex,typename... More>
		void operator()(Typex &_Val,More &... _More){
			*this>>_Val;
			operator()(_More...);
		}
		void pop(){
			char ch;
			Get_Char(ch);
		}
		char peek(){
			if(_Start_ptr==_End_ptr){
				_Start_ptr=_Buf;
				_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);
			}
			if(_Start_ptr==_End_ptr){
				_Ok=0;
				return -1;
			}else return *_Start_ptr;
		}
		template <typename Typex>
		void operator()(Typex &_Val){*this>>_Val;}
		template <typename Typex,typename...More>
		streambuf *rdbuf(){return inbuf;}
		void rdbuf(streambuf *_inbuf){inbuf=_inbuf;}
		Fast_Istream getline(string &s,char _End='\n'){
			if(_Ok){
				char c;
				Get_Char(c);
				while((c==32||c==10||c==13||c==8||c==9||c==7||c==12||c==11||c==-1)&&c!=_End) Get_Char(c);
				for(s.clear();c!=_End&&~c;Get_Char(c)) s.push_back(c);
				--_Start_ptr;
			}
			return *this;
		}
	};
}
//快写
namespace Fast_O{
	string buf;
	streambuf *outbuf;
	int _M_precision=6;
	struct Fast_Ostream{
		Fast_Ostream(streambuf *out,unsigned int Size){
			buf.reserve(Size);
			outbuf=out;
		}
		Fast_Ostream(std::streambuf* out){outbuf=out;}
		Fast_Ostream(const char *File,unsigned int Size){
			buf.reserve(Size);
			rdbuf(File);
		}
		void rdbuf(const char *File){
			static ofstream __Out__(File);
			rdbuf(__Out__.rdbuf());
		}
		Fast_Ostream(unsigned int Size){buf.reserve(Size);}
		void flush(){
			outbuf->sputn(buf.data(),buf.size());
			buf.clear();
		}
		~Fast_Ostream(){flush();}
		void endl(){buf.push_back('\n');}
		Fast_Ostream &operator<<(char _Val){
			buf.push_back(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(const char *_Val){
			while(*_Val) buf.push_back(*_Val++);
			return *this;
		}
		Fast_Ostream &operator<<(const string &_Val){
			buf+=_Val;
			return *this;
		}
		template <typename Typex>
		void Put_Unsigned(Typex _Val){
			char *_Stack=(char *)malloc(sizeof(Typex)*3);
			unsigned S_top=0;
			while(_Val){
				_Stack[++S_top]=(_Val%10)^48;
				_Val/=10;
			}
			if(!S_top) buf.push_back('0');
			while(S_top) buf.push_back(_Stack[S_top--]);
			free(_Stack);
		}
		template <typename Typex>
		void Put_Int(Typex _Val){
			if(_Val<0){
				buf.push_back('-');
				Put_Unsigned(~_Val+1);
			}else Put_Unsigned(_Val);
		}
		Fast_Ostream &operator<<(bool _Val){
			buf.push_back(_Val?'1':'0');
			return *this;
		}
		Fast_Ostream &operator<<(short _Val){
			Put_Int(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(int _Val){
			Put_Int(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(long _Val){
			Put_Int(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(long long _Val){
			Put_Int(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(unsigned short _Val){
			Put_Unsigned(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(unsigned int _Val){
			Put_Unsigned(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(unsigned long _Val){
			Put_Unsigned(_Val);
			return *this;
		}
		Fast_Ostream &operator<<(unsigned long long _Val){
			Put_Unsigned(_Val);
			return *this;
		}
		template <typename Typex>
		void endl(const Typex &_Val){*this<<_Val<<'\n';}
		template <typename Typex,typename... More>
		void endl(const Typex &_Val,const More &... _More){
			*this<<_Val;
			endl(_More...);
		}
		template <typename Typex>
		void operator()(const Typex &_Val){*this<<_Val;}
		template <typename Typex,typename... More>
		void operator()(const Typex &_Val,const More &... _More){
			*this<<_Val;
			operator()(_More...);
		}
		std::streambuf *rdbuf(){return outbuf;}
		void rdbuf(std::streambuf *_outbuf){outbuf=_outbuf;}
	};
}
namespace Fast_IO{
	Fast_I::Fast_Istream fin(cin.rdbuf(),16777216);
	Fast_O::Fast_Ostream fout(cout.rdbuf());
}
```

# 高精

太多了写不下，去看[这里](https://www.luogu.com.cn/article/1btyfn75)

# 排序
## 桶排序
```cpp
for(int i=0;i<1000;i++){
  int x;
  cin>>x;
  a[x]++;
}
for(int i=1000;i>=1;i--){
  for(int j=1;j<=a[i];j++){
    cout<<i<<' ';
  }
}
```
## 冒泡排序
```cpp
for(int i=1;i<n;i++){
  for(int j=1;j<=n-i;j++){
    if(a[j]>a[j+1]){
      swap(a[j],a[j+1]);
    }
  }
}
```
## 选择排序
```cpp
for(int i=1;i<=n-1;i++){
  k=i;
  for(int j=i+1;j<=n;j++){
    if(a[k]>a[j]) k=j;
  }
  if(k!=i) swap(a[k],a[i]);
}
```
## 归并排序

```cpp
void merge(int l,int r){
	if(l==r) return;//边界 
	int mid=(l+r)>>1;//取mid将区间一分为二 
	merge(l,mid),merge(mid+1,r);//分而治之 
	int ans[MAXN];//建立一个临时数组当“罐子” 
	int i=l,j=mid+1,k=l;
	for(;i<=mid&&j<=r&&k<=r;k++){
		if(a[i]<=a[j]){//比较大小找出较小数 
			ans[k]=a[i];//把小的数往罐子里倒 
			i++; 
		}else{
			ans[k]=a[j];
			j++;
		}
	}
	for(;i<=mid;i++) ans[k++]=a[i];//没把所有数都倒进去，接着倒 
	for(;j<=r;j++) ans[k++]=a[j];
	for(int i=l;i<=r;i++){
		a[i]=ans[i];//最后倒回去 
	}
}
```

## 快排
```cpp
void Quicksort(int num[], int left, int right){
    if (right <= left) return;
    int i = left;
    int j = right;
    int key = num[left];
    while (1){
        //从左向右找比key大的值*/
        while (num[i] <= key){
            i++;
            if (i == right) break;
        }
        //从右向左找比key小的值
        while (num[j] >= key){
            j--;
            if (j == left) break;
        }
        if (i >= j) break;
        //交换i,j对应的值
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    //中枢值与j对应值交换
    num[left] = num[j];
    num[j] = key;
    Quicksort(num, left, j - 1);
    Quicksort(num, j + 1, right);
}
```
## sort排序
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<' ';
	}
	return 0;
} 
```
# 前缀和
## 一维前缀和

```cpp
//从x加到y
sum[i]=sum[i-1]+a[i];
ans=sum[y]-sum[x-1];
```

## 假二维前缀和
```cpp
//从(x1,y1)加到(x2,y2)
sum[i][j]=sum[i][j-1]+a[i][j];		
for(int i=x1;i<=x2;i++){
  ans+=sum[i][y2]-sum[i][y1-1];
}
```
## 二维前缀和

```cpp
//从(x1,y1)加到(x2,y2)
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
```

## 假三维前缀和

```cpp
//从(x,y,z)加到(x_,y_,z_)
sum[i][j][k]=sum[i][j-1][k]+sum[i][j][k-1]+a[i][j][k]-sum[i][j-1][k-1];
for(int i=x;i<=x_;i++){
  ans+=sum[i][y_][z_]-sum[i][y-1][z_]-sum[i][y_][z-1]+sum[i][y-1][z-1];
}
```

# 实用程序
## `int` 矩阵结构体
```cpp
const int N=55;
struct matrix{
	int n,m;
	int a[N][N];
	int sum[N][N];
	int tmp[N][N];
	int find(matrix where,int x,int y){
		return where.a[x][y];
	}
	void input(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
			}
		}
	}
	void output(){
		for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}
	}
	void turn_left(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				tmp[i][j]=a[j][4-i];
			}
		}
		memcpy(a,tmp,sizeof(tmp));
	} 
	void turn_right(){
		for(int i=1;i<=3;i++) turn_left();
	}
	void flip_top(){
		for(int i=1;i<=n/2;i++){
			for(int j=1;j<=m;j++){
				swap(a[i][j],a[n+1-i][j]);
			}
		}
	}
	void flip_left(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m/2;j++){
				swap(a[i][j],a[i][m+1-j]);
			}
		}
	}
	long long getSum(int x,int y,int x_,int y_){
		long long ret;
		ret=sum[x_][y_]-sum[x-1][y_]-sum[x_][y-1]+sum[x-1][y-1];
		return ret;
	}
};
```
## 更改剪切板
```cpp
void Copy(string TempBin){
    HGLOBAL hMemBin=NULL;
    PCHAR LockBin=NULL;
    OpenClipboard(NULL);
    EmptyClipboard();
    hMemBin=GlobalAlloc(GMEM_MOVEABLE,TempBin.size()+1);
    LockBin=(PCHAR)GlobalLock(hMemBin);
    RtlMoveMemory(LockBin,TempBin.c_str(),TempBin.size()+1);
    GlobalUnlock(hMemBin);
    LockBin=NULL;
    SetClipboardData(CF_TEXT,hMemBin);
    CloseClipboard();
}
```

# 树论
## LCA
### 暴力跳

```cpp
void dfs(int x,int from){//求深度
	deep[x]=deep[from]+1;
	f[x]=from;
	for(int i=0;i<tree[x].size();i++){
		int to=tree[x][i];
		if(from==to) continue;
		dfs(to,x);
	}
}
int lca(int x,int y){
	if(deep[x]>deep[y]) swap(x,y);
	while(deep[x]>deep[y]) y=f[y];
	if(x==y) return x;
	while(x!=y) x=f[x],y=f[y];
	return x;
}
```
### 倍增

```cpp
void dfs(int x,int from){//求深度
	deep[x]=deep[from]+1;
	f[x][0]=from;
	for(int i=1;i<20;i++){
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(int i=0;i<tree[x].size();i++){
		int to=tree[x][i];
		if(from==to) continue;
		dfs(to,x);
	}
}
int lca(int x,int y){
	if(deep[x]>deep[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(deep[f[y][i]]>=deep[x]) y=f[y][i];
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
```

# 图论
## 存储图
### 链式前向星

```cpp
struct Edge{
	int to,w,nxt;
}e[MAXM];
int head[MAXN],num;
void add(int from,int to,int w){
	e[++num]=(Edge){to,w,head[from]};
	head[from]=num;
}
```

## 最短路

||BFS|dij|dij+堆|Bellman-Ford|Floyd|SPFA|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|注|边权为1|边权非负|边权非负||慢|被菊花图卡|
|时间|$n+m$|$n^2$|$m \log m$|$nm$|$n^3$|$m \le SPFA \le nm$|
|n,m范围||$n<5000$|$m<1e6,n>1e4$|$nm<1e9$|$n<400$|$m<1e6,n>1e4$|
|其他|单源|单源|单源|单源|多源|单源|

### Bellman-Ford优化

```cpp
struct Edge{
	int from,to,w;
}e[500005];//注意！！！如果是无向图开2倍 
int n,m,s,u,v,w;
int d[10005];
int main(){
	cin>>n>>m>>s;
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[i]=(Edge){u,v,w};
		if(u==s) d[v]=w;
	}d[s]=0;
	//Bellman-Ford
	for(int i=1;i<=n-1;i++){
		bool check=0;//注意，这里增加了一个布尔变量 
		for(int j=1;j<=m;j++){
//			d[e[j].to]=min(d[e[j].to],e[j].w+d[e[j].from]);
			if(d[e[j].to]>e[j].w+d[e[j].from]){
				check=1;
				d[e[j].to]=e[j].w+d[e[j].from];
			}
		}
		if(check==0) break;
	}
	for(int i=1;i<=n;i++){
		if(d[i]==0x3f3f3f3f) cout<<0x7fffffff<<' ';
		else cout<<d[i]<<' ';
	}
```

### 堆优dijkstra+邻接表

```cpp
struct node{
	int v,w;
	friend bool operator< (node x,node y){
		return x.w>y.w;
	}
};
vector<node> G[100005];
void dij(int s){
	for(int i=1;i<=n;i++) ans[i]=INF;
	ans[s]=0;
	priority_queue<node> q;
	q.push((node){s,0});
	while(!q.empty()){
		int u=q.top().v;q.pop();
		if(vis[u]) continue;vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v,w=G[u][i].w;
			if(ans[v]>ans[u]+w){
				ans[v]=ans[u]+w;
				q.push((node){v,ans[v]});
			}
		}
	}
}
```

### 堆优dijkstra+链式前向星

```cpp
//链式前向星 
struct Edge{
	int to,w,next;
}e[200005];

struct Node{
	int x,y;
	friend bool operator < (Node a,Node b){
		return a.y>b.y;
	}
};

int head[100005];
int d[100005];
int num,n,m,s,u,v,w;
void addEdge(int from,int to,int w){
	e[++num]=(Edge){to,w,head[from]};
	head[from]=num;
	return; 
}

//Dijkstra
priority_queue<Node> q;
void dij(int s){
	memset(d,0x3f,sizeof(d));
	for(int i=head[s];i;i=e[i].next){
		d[e[i].to]=e[i].w;
	}
	d[s]=0;
	f[s]=1;
	while(!q.empty()){
		int x=q.top().x;q.pop();
		if(f[x]==1) continue;
		f[x]=1;
		for(int i=head[x];i;i=e[i].next){
			if(d[e[i].to]>d[x]+e[i].w){
				d[e[i].to]=d[x]+e[i].w;
				q.push((Node){e[i].to,d[e[i].to]});
			}
		}
	}
} 
```

## 二分图

### 匈牙利算法

```cpp
bool find(int x){
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(vis[to]) continue;//连过了 
		vis[to]=1;
		if(line[to]==-1||find(line[to])){//没连过或可以找别的 
			line[to]=x;//连上 
			return 1;
		}
	}
	return 0;
}
int hungary(){
	memset(line,-1,sizeof(line));
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(find(i)) ans++;//能找到 
	}
	return ans;
}
```

## 网络最大流

```cpp
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define int long long
using namespace std;
const ll inf=LONG_LONG_MAX;
int n,m,s,t; 
int ans=0;
struct Edge{
	int to,w,nxt;
}e[10005];
int num=1,head[205];
void add(int from,int to,int w){
	e[++num]=(Edge){to,w,head[from]};
	head[from]=num;
}
int dis[205],now[205];
bool bfs(){//构造分层图 
	for(int i=1;i<=n;i++) dis[i]=inf;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	now[s]=head[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(e[i].w&&dis[to]==inf){
				q.push(to);
				now[to]=head[to];
				dis[to]=dis[x]+1;
				if(to==t) return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,int sum){//sum是整条增广路对最大流的贡献 
	if(x==t) return sum;
	int ans=0;
	for(int i=now[x];i&&sum;i=e[i].nxt){
		now[x]=i;//当前弧优化 
		int to=e[i].to;
		if(e[i].w&&(dis[to]==dis[x]+1)){
			int k=dfs(to,min(sum,e[i].w));//当前最小的剩余容量 
			if(k==0) dis[to]=inf;//剪枝，去掉增广完毕的点 
			e[i].w-=k;
			e[i^1].w+=k;
			ans+=k;//经过该点的所有流量和 
			sum-=k;//经过该点的剩余流量 
		} 
	}
	return ans; 
}
signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,0);
	}
	while(bfs()) ans+=dfs(s,inf);
	cout<<ans<<endl;
	return 0;
}
```

# dp
## 01背包
```cpp
for(int i=1;i<=m;i++){
	for(int j=t;j>=w[i];j--){
		dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
	}
}
```
## 01背包算方案数

```cpp
dp[0]=1;//dp[j]为凑到重量为j的方案数
for(int i=1;i<=n;i++){
	for(int j=m,j>=a[i];j--){
		dp[j]+=dp[j-a[i]];
	}
} 
```

## 完全背包
```cpp
for(int i=1;i<=m;i++){
	for(int j=w[i];j<=t;j++){
		dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
	}
}
```

## 多重背包+二进制优化

```cpp
cin>>n>>m;
for(int i=1;i<=n;i++){
  cin>>a>>b>>s;
  for(int j=1;j<=s;j*=2){
    num++;
    //放入体积、价值 
    w[num]=a*j;
    c[num]=b*j;
    s-=j;//一直往下扣2^n 
  }
  if(s!=0){
    //没放完，把最后的常数放进去 
    num++;
    w[num]=a*s;
    c[num]=b*s;
  }
}
//01
for(int i=1;i<=num;i++){
  for(int j=m;j>=w[i];j--){
    dp[j]=max(dp[j],dp[j-w[i]]+c[i]);//经典01背包模板 
  }
}
```

本博客还未完善，如有错误欢迎指正！