建议用标题旁边打开的目录，更清晰明了！
其他
读入、输出优化（必加！！！）
快读
模板
inline int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
快输
模板
void print(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
数据结构
树剖
平衡树
Splay
点击查看代码
//超级全，啥都有
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
struct node{
int son[2],cnt,val,tot,fa;
}tr[N];
int co,root;
int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
inline void pushup(int x){
tr[x].tot=tr[tr[x].son[0]].tot+tr[tr[x].son[1]].tot+tr[x].cnt;
}
inline void rotate(int x){
int y=tr[x].fa,z=tr[y].fa,k=(tr[y].son[1]==x);
tr[z].son[tr[z].son[1]==y]=x;
// cout<<"rotate: "<<x<<" "<<z<<" "<<tr[x].val<<" "<<tr[z].val<<endl;
tr[x].fa=z;
tr[y].son[k]=tr[x].son[k^1];
tr[tr[x].son[k^1]].fa=y;
tr[x].son[k^1]=y;
tr[y].fa=x;
pushup(y),pushup(x);
}
void splay(int x,int goal){
while(tr[x].fa!=goal){
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal)
((tr[y].son[1]==x)^(tr[z].son[1]==y))?rotate(x):rotate(y);
rotate(x);
}
if(!goal) root=x;
}
void fi(int x){
int u=root;
if(!u) return;
while(tr[u].son[x>tr[u].val] && tr[u].val!=x)
u=tr[u].son[x>tr[u].val];
splay(u,0);
}
void insert(int x){
int fa=0,u=root;
while(u && tr[u].val!=x){
fa=u;
u=tr[u].son[x>tr[u].val];
}
// cout<<"insert : "<<x<<" "<<u<<" "<<fa<<" "<<tr[u].val<<" "<<tr[fa].val<<endl;
if(u) tr[u].cnt++;
else{
u=++co;
if(fa) tr[fa].son[x>tr[fa].val]=u;
tr[u].fa=fa,tr[u].son[0]=tr[u].son[1]=0;
tr[u].cnt=1,tr[u].tot=1,tr[u].val=x;
}
splay(u,0);
}
int nxt(int x,bool k){
fi(x);
int u=root;
if(tr[u].val>x && k) return u;
if(tr[u].val<x && !k) return u;
u=tr[u].son[k];
while(tr[u].son[k^1]) u=tr[u].son[k^1];
return u;
}
void delet(int x){
int pre=nxt(x,0),suc=nxt(x,1);
splay(pre,0),splay(suc,pre);
int del=tr[suc].son[0];
if(tr[del].cnt>1){
tr[del].cnt--;
splay(del,0);
}
else tr[suc].son[0]=0;
}
int rk(int x){
fi(x);
return tr[tr[root].son[0]].tot+1;
}
int kth(int p,int x){
// cout<<"kth : "<<p<<" "<<tr[p].tot<<" "<<tr[p].val<<" "<<x<<endl;
if(tr[p].tot<x) return 0;
if(tr[tr[p].son[0]].tot>=x) return kth(tr[p].son[0],x);
if(tr[tr[p].son[0]].tot+tr[p].cnt>=x) return tr[p].val;
return kth(tr[p].son[1],x-tr[tr[p].son[0]].tot-tr[p].cnt);
}
int main(){
insert(-INF),insert(INF);
int n=read(),op,x;
while(n--){
op=read(),x=read();
if(op==1) insert(x);
if(op==2) delet(x);
if(op==3) printf("%d\n",rk(x)-1);
if(op==4) printf("%d\n",kth(root,x+1));
if(op==5) printf("%d\n",tr[nxt(x,0)].val);
if(op==6) printf("%d\n",tr[nxt(x,1)].val);
}
return 0;
}
线段树
单点加减，区间询问
模板
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=1e5+5;
int tr[N<<2];
void pushup(int node){
tr[node]=tr[node<<1]+tr[node<<1|1];
}
void change(int node,int l,int r,int x,int y){
if(l>x || r<x) return;
if(l==r && l==x){
tr[node]+=y;
return;
}
change(node<<1,l,mid,x,y);
change(node<<1|1,mid+1,r,x,y);
pushup(node);
}
int ask(int node,int l,int r,int be,int en){
if(l>en || r<be) return 0;
if(l>=be && r<=en) return tr[node];
return ask(node<<1,l,mid,be,en)+ask(node<<1|1,mid+1,r,be,en);
}
int main(){
int n,m;
cin>>n>>m;
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op) cout<<ask(1,1,n,x,y)<<endl;
else change(1,1,n,x,y);
}
return 0;
}
区间加减，区间询问
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define int long long
const int N=1e6+5;
int tr[N<<2],lz[N<<2],len[N<<2];
int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
void print(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
void pushup(int node){
tr[node]=tr[node<<1]+tr[node<<1|1];
}
void push(int node,int x){
tr[node]+=len[node]*x,lz[node]+=x;
}
void pushdown(int node){
if(lz[node]){
push(node<<1,lz[node]);
push(node<<1|1,lz[node]);
lz[node]=0;
}
}
void build(int node,int l,int r){
len[node]=r-l+1;
if(l==r){
tr[node]=read();
return;
}
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
pushup(node);
}
void change(int node,int l,int r,int be,int en,int x){
if(l>en || r<be) return;
if(l>=be && r<=en){
push(node,x);
return;
}
pushdown(node);
change(node<<1,l,mid,be,en,x);
change(node<<1|1,mid+1,r,be,en,x);
pushup(node);
}
int ask(int node,int l,int r,int be,int en){
if(l>en || r<be) return 0;
if(l>=be && r<=en) return tr[node];
pushdown(node);
return ask(node<<1,l,mid,be,en)+ask(node<<1|1,mid+1,r,be,en);
}
signed main(){
int n,m;
n=read(),m=read();
build(1,1,n);
while(m--){
int op,x,y,z;
op=read(),x=read(),y=read();
if(op==2) print(ask(1,1,n,x,y)),puts("");
else z=read(),change(1,1,n,x,y,z);
}
return 0;
}
区间加乘，区间询问
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define int long long
const int N=1e5+5;
int p;
int tr[N<<2],lz_add[N<<2],lz_mul[N<<2],len[N<<2];
int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
void pushup(int node){
tr[node]=(tr[node<<1]%p+tr[node<<1|1]%p)%p;
}
void push_add(int node,int x){
tr[node]+=len[node]*x,tr[node]%=p;
lz_add[node]+=x,lz_add[node]%=p;
}
void push_mul(int node,int x){
tr[node]*=x,tr[node]%=p;
lz_mul[node]*=x,lz_mul[node]%=p;
lz_add[node]*=x,lz_add[node]%=p;
}
void pushdown(int node){
if(lz_mul[node]!=1){
push_mul(node<<1,lz_mul[node]);
push_mul(node<<1|1,lz_mul[node]);
lz_mul[node]=1;
}
if(lz_add[node]){
push_add(node<<1,lz_add[node]);
push_add(node<<1|1,lz_add[node]);
lz_add[node]=0;
}
}
void build(int node,int l,int r){
len[node]=r-l+1;
lz_mul[node]=1;
if(l==r){
tr[node]=read()%p;
return;
}
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
pushup(node);
}
void change_mul(int node,int l,int r,int be,int en,int x){
if(l>en || r<be) return;
if(l>=be && r<=en){
push_mul(node,x);
return;
}
pushdown(node);
change_mul(node<<1,l,mid,be,en,x);
change_mul(node<<1|1,mid+1,r,be,en,x);
pushup(node);
}
void change_add(int node,int l,int r,int be,int en,int x){
if(l>en || r<be) return;
if(l>=be && r<=en){
push_add(node,x);
return;
}
pushdown(node);
change_add(node<<1,l,mid,be,en,x);
change_add(node<<1|1,mid+1,r,be,en,x);
pushup(node);
}
int ask(int node,int l,int r,int be,int en){
if(l>en || r<be) return 0;
if(l>=be && r<=en) return tr[node]%p;
pushdown(node);
return (ask(node<<1,l,mid,be,en)+ask(node<<1|1,mid+1,r,be,en))%p;
}
signed main(){
int n,m;
n=read(),p=read();
build(1,1,n);
m=read();
while(m--){
int op,x,y,z;
op=read(),x=read(),y=read();
if(op==1) z=read(),change_mul(1,1,n,x,y,z);
if(op==2) z=read(),change_add(1,1,n,x,y,z);
if(op==3) printf("%lld\n",ask(1,1,n,x,y));
}
return 0;
}
扫描线
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
const int N=2e5+5;
int ly[N];
struct seg{
int x,y[2];
int val;
}a[N];
int len[N<<4],tr[N<<4],sum[N<<4];
inline int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
bool cmp(seg _,seg __){
return _.x<__.x;
}
void build(int node,int l,int r){
len[node]=ly[r+1]-ly[l];
if(l==r) return;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
}
void pushup(int node){
if(sum[node])
tr[node]=len[node];
else
tr[node]=tr[node<<1]+tr[node<<1|1];
}
void change(int node,int l,int r,int be,int en,int x){
if(l>en || r<be) return;
if(l>=be && r<=en){
sum[node]+=x;
pushup(node);
return;
}
change(node<<1,l,mid,be,en,x);
change(node<<1|1,mid+1,r,be,en,x);
pushup(node);
}
signed main(){
int n=read();
for(int i=1;i<=n;++i){
a[i].x=read(),a[i].y[0]=a[i+n].y[0]=ly[i]=read();
a[i+n].x=read(),a[i].y[1]=a[i+n].y[1]=ly[i+n]=read();
a[i].val=1,a[i+n].val=-1;
}
n*=2;
sort(a+1,a+n+1,cmp);
sort(ly+1,ly+n+1);
int co=unique(ly+1,ly+n+1)-ly-1;
ly[co+1]=0x3f3f3f3f;
build(1,1,co);
int ans=0;
for(int i=1;i<n;++i){
int y=lower_bound(ly+1,ly+co+1,a[i].y[0])-ly;
int y1=lower_bound(ly+1,ly+co+1,a[i].y[1])-ly-1;
//cout<<y<<" "<<y1<<endl;
change(1,1,co,y,y1,a[i].val);
ans+=tr[1]*(a[i+1].x-a[i].x);
//cout<<a[i].x<<" "<<a[i].val<<" "<<ans<<endl;
}
printf("%lld",ans);
return 0;
}
树状数组
区间加减，区间询问
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int t1[N],t2[N];
int n;
int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
void print(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
void add(int x,int y){
for(int i=x;i<=n;i+=(i&-i)) t1[i]+=y;
for(int i=x;i<=n;i+=(i&-i)) t2[i]+=x*y;
}
int ask(int x){
int res=0,tmp=0;
for(int i=x;i;i-=(i&-i)) res+=t1[i];
res*=(x+1);
for(int i=x;i;i-=(i&-i)) tmp+=t2[i];
return res-tmp;
}
signed main(){
int m;
n=read(),m=read();
++n;
for(int i=2;i<=n;++i){
int x=read();
add(i+1,-x),add(i,x);
}
while(m--){
int op,x,y,z;
op=read(),x=read(),y=read();
if(op==2) ++x,++y,print(ask(y)-ask(x-1)),puts("");
else ++y,++x,z=read(),add(y+1,-z),add(x,z);
}
return 0;
}
图论
最小环
Floyd 求最小环+输路径
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[105][105],d[105][105],pa[105][105],ans[105];
int mi=1e9,co;
void get_pa(int x,int y){
if(!pa[x][y]) return;
get_pa(x,pa[x][y]);
ans[++co]=pa[x][y];
get_pa(pa[x][y],y);
}
signed main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) a[i][j]=d[i][j]=1e9;
for(int i=1;i<=m;++i){
int x,y,z;cin>>x>>y>>z;
a[x][y]=a[y][x]=d[x][y]=d[y][x]=min(z,d[x][y]);
}
for(int k=1;k<=n;++k){
for(int i=1;i<k;++i)
for(int j=i+1;j<k;++j)
if(d[i][j]+a[i][k]+a[k][j]<mi){
mi=d[i][j]+a[i][k]+a[k][j];
co=0;
get_pa(i,j),ans[++co]=j,ans[++co]=k,ans[++co]=i;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
pa[i][j]=k;
}
}
if(mi==1e9) cout<<"No solution.";
else for(int i=1;i<=co;++i) cout<<ans[i]<<" ";
return 0;
}
LCA
倍增求LCA
点击查看代码
const int N=5e5+5;
int fa[N][30],d[N];
int s=1;
vector<int> ed[N];
void bfs(){
queue<int> q;
q.push(s);d[0]=-1e9;
while(q.size()){
int x=q.front();q.pop();
for(int i=0;i<(int)ed[x].size();++i){
int y=ed[x][i];
if(y==s || d[y]) continue;
d[y]=d[x]+1;q.push(y);
fa[y][0]=x;
for(int j=1;j<=20;++j)
fa[y][j]=fa[fa[y][j-1]][j-1];
}
}
}
int lca(int x,int y){
if(d[y]>d[x]) swap(x,y);
for(int i=20;i>=0;--i)
if(d[fa[x][i]]>=d[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
Tarjan
桥
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//桥一定要去重边！！！
const int N=2e3+5,M=2e6+5;
int dfn[N],low[N],cnt;
int h[N],nxt[M],ver[M],st[M],co;
bool a[N][N];
int n,m;
set<pair<int,int> > s;
void add(int x,int y){
nxt[++co]=h[x],h[x]=co,ver[co]=y,st[co]=x;
}
int tarjan(int x,int fa){
dfn[x]=++cnt,low[x]=cnt;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa) continue;
if(dfn[y]) low[x]=min(low[x],low[y]);
else low[x]=min(low[x],tarjan(y,x));
if(low[y]>dfn[x]) s.insert(make_pair(min(st[i],ver[i]),max(st[i],ver[i])));
}
return low[x];
}
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y;cin>>x>>y;
if(a[x][y]) continue;
add(x,y),add(y,x),a[x][y]=a[y][x]=1;
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i,0);
cout<<s.size()<<endl;
for(auto it:s)
cout<<it.first<<" "<<it.second<<endl;
return 0;
}
割点
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//割点不用去重边！！！
const int N=2e4+5,M=1e5+5;
vector<int> ed[N];
int dfn[N],low[N],cnt;
set<int> s;
int tarjan(int x,int fa){
low[x]=dfn[x]=++cnt;
int co=0;
for(int i=0;i<ed[x].size();++i){
int y=ed[x][i];
if(y==fa) continue;
if(!dfn[y]){
low[x]=min(low[x],tarjan(y,x)),++co;
if(fa && low[y]>=dfn[x]) s.insert(x);
}
else low[x]=min(low[x],dfn[y]);
}
if(!fa && co>1) s.insert(x);
return low[x];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y;cin>>x>>y;
ed[x].push_back(y);
ed[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i,0);
cout<<s.size()<<endl;
for(auto it:s) cout<<it<<" ";
return 0;
}
缩点、Tarjan 求强联通分量
点击查看代码
//Luogu P3387 【模板】缩点
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e5+5;
vector<int> ed[N],e[N];
int dfn[N],low[N],st[N],top,cnt;
bool vi[N];
int a[N],ans;
int w[N],co,d[N],f[N],dp[N];
int n,m;
struct edge{
int x,y;
}edg[M];
int tarjan(int x){
dfn[x]=low[x]=++cnt;
st[++top]=x;
vi[x]=1;
for(int i=0;i<ed[x].size();++i){
if(vi[ed[x][i]]) low[x]=min(low[x],low[ed[x][i]]);
if(!dfn[ed[x][i]]) low[x]=min(low[x],tarjan(ed[x][i]));
}
if(dfn[x]==low[x]){
int sum=a[x];
while(top && st[top]!=x)
f[st[top]]=x,sum+=a[st[top]],vi[st[top]]=0,--top;
--top,vi[x]=0,f[x]=x;
w[x]=sum;
}
return low[x];
}
void topo(){
queue<int> q;
for(int i=1;i<=n;++i)
if(f[i]==i && !d[i]) q.push(i),dp[i]=w[i];
while(q.size()){
int x=q.front();q.pop();
ans=max(ans,dp[x]);
for(int i=0;i<e[x].size();++i){
int y=e[x][i];
dp[y]=max(dp[y],dp[x]+w[y]);
d[y]--;
if(!d[y]) q.push(y);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=m;++i){
cin>>edg[i].x>>edg[i].y;
ed[edg[i].x].push_back(edg[i].y);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;++i)
if(f[edg[i].x]!=f[edg[i].y]){
d[f[edg[i].y]]++;
e[f[edg[i].x]].push_back(f[edg[i].y]);
}
topo();
cout<<ans;
return 0;
}
基环树
拓扑排序找环（无向图）
模板
void topo(int x){
queue<int> q;
for(int i=1;i<=n;++i)
if(d[i]==1) q.push(cal[x][i]);
while(q.size()){
int y=q.front();q.pop();
for(int i=0;i<ed[y].size();++i){
int z=ed[y][i];
if(d[z]<=1) continue;
--d[z];
if(d[z]==1) q.push(z);
}
}
for(int i=1;i<=n;++i)
if(d[i]>1) ++cnt;
}
二分图
二分图最大匹配（匈牙利算法）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=505,M=5e4+5;
int h[N],nxt[M],en[M],co;
bool v[N];
int match[N];
void add(int a,int b){
nxt[++co]=h[a],en[co]=b,h[a]=co;
}
bool dfs(int x){
for(int i=h[x];i;i=nxt[i])
if(!v[en[i]]){
v[en[i]]=1;
if(!match[en[i]] || dfs(match[en[i]])){
match[en[i]]=x;
return 1;
}
}
return 0;
}
int main(){
int n,m,e;
cin>>n>>m>>e;
for(int i=1;i<=e;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
int ans=0;
for(int i=1;i<=n;i++){
memset(v,0,sizeof v);
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}
网络流
最大流、最小费用最大流、最小割
Dinic（最大网络流=最小割）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e3+5,INF=0x3f3f3f3f;
int nxt[N],h[M],w[N],ver[N],co=1;
int n,m,s,t;
int d[M],no[M];
inline int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
void add(int x,int y,int z){
nxt[++co]=h[x],h[x]=co,ver[co]=y,w[co]=z;
nxt[++co]=h[y],h[y]=co,ver[co]=x,w[co]=0;
}
bool bfs(){
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1,no[s]=h[s];
while(q.size()){
int x=q.front();q.pop();
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(!d[y] && w[i]){
d[y]=d[x]+1;
no[y]=h[y];
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rest=flow,k,i;
for(i=no[x];i && rest;i=nxt[i]){
int y=ver[i];
if(d[y]==d[x]+1 && w[i]){
k=dfs(y,min(rest,w[i]));
if(!k) d[y]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
}
}
no[x]=i;
return flow-rest;
}
int main(){
n=read(),m=read();
s=1,t=n;
for(int i=1;i<=m;++i){
int x=read(),y=read(),z=read();
add(x,y,z);
}
int ans=0,flow=0;
while(bfs())
while(flow=dfs(1,INF))
ans+=flow;
cout<<ans<<endl;
return 0;
}
EK（最小费用流）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=1e5+5,INF=0x3f3f3f3f;
int nxt[M],h[N],ver[M],w[M],fl[M];
int n,m,s,t,co=1;//co=1!!!!!!!
bool vi[N];
int pre[N],dis[N];
inline int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
void add(int x,int y,int z,int d){
nxt[++co]=h[x],h[x]=co,ver[co]=y,w[co]=z,fl[co]=d;
nxt[++co]=h[y],h[y]=co,ver[co]=x,w[co]=-z,fl[co]=0;
}
bool spfa(){
memset(dis,0x3f,sizeof dis);
memset(vi,0,sizeof vi);
queue<int> q;
vi[s]=1,dis[s]=0;
q.push(s);
while(q.size()){
int x=q.front();q.pop();
vi[x]=0;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(dis[y]>dis[x]+w[i] && fl[i]){
pre[y]=i;
dis[y]=dis[x]+w[i];
if(vi[y]) continue;
vi[y]=1;
q.push(y);
}
}
}
if(dis[t]==INF) return 0;
return 1;
}
int main(){
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int x,y,z,d;
x=read(),y=read(),d=read(),z=read();
add(x,y,z,d);
}
int flow=0,ans=0;
while(spfa()){
int p,mi=INF;
for(int i=t;i!=s;i=ver[p^1]){
p=pre[i];
mi=min(mi,fl[p]);
}
for(int i=t;i!=s;i=ver[p^1]){
p=pre[i];
fl[p]-=mi;
fl[p^1]+=mi;
ans+=w[p]*mi;
}
flow+=mi;
}
cout<<flow<<" "<<ans;
return 0;
}
上下界网络流
无汇源上下界可行流
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,INF=0x3f3f3f3f;
int h[N],nxt[N],ver[N],w[N],co=1;
int in[N],out[N];
int c[N],D[N];
int s,t,n,m;
int d[N],no[N];
void add(int x,int y,int z){
nxt[++co]=h[x],h[x]=co,ver[co]=y,w[co]=z;
nxt[++co]=h[y],h[y]=co,ver[co]=x,w[co]=0;
}
bool bfs(){
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1,no[s]=h[s];
while(q.size()){
int x=q.front();q.pop();
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(!d[y] && w[i]){
d[y]=d[x]+1;
no[y]=h[y];
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rest=flow,k,i;
for(i=no[x];i && rest;i=nxt[i]){
int y=ver[i];
if(d[y]==d[x]+1 && w[i]){
k=dfs(y,min(rest,w[i]));
if(!k) d[y]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
}
}
no[x]=i;
return flow-rest;
}
int main(){
int a,b;
cin>>n>>m;
s=n+1,t=s+1;
for(int i=1;i<=m;++i){
cin>>a>>b>>c[i]>>D[i];
add(a,b,D[i]-c[i]);
in[b]+=c[i],out[a]+=c[i];
}
int sum=0;
for(int i=1;i<=n;++i){
if(in[i]>out[i]) add(s,i,in[i]-out[i]),sum+=in[i]-out[i];
if(out[i]>in[i]) add(i,t,out[i]-in[i]);
}
int ans=0,flow=0;
while(bfs()){
while(flow=dfs(s,INF)) ans+=flow;
}
if(ans!=sum){
cout<<"NO";
return 0;
}
cout<<"YES"<<endl;
for(int i=2;i<=m*2;i+=2)
cout<<D[i/2]-w[i]<<endl;
return 0;
}
有汇源有上下界最小流
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e3+5,INF=0x3f3f3f3f;
int nxt[N],h[M],w[N],ver[N],co=1;
int n,m,s,t;
int in[N],out[N];
int d[M],no[M];
void add(int x,int y,int z){
nxt[++co]=h[x],h[x]=co,ver[co]=y,w[co]=z;
nxt[++co]=h[y],h[y]=co,ver[co]=x,w[co]=0;
}
bool bfs(){
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1,no[s]=h[s];
while(q.size()){
int x=q.front();q.pop();
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(!d[y] && w[i]){
d[y]=d[x]+1;
no[y]=h[y];
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rest=flow,k,i;
for(i=no[x];i && rest;i=nxt[i]){
int y=ver[i];
if(d[y]==d[x]+1 && w[i]){
k=dfs(y,min(rest,w[i]));
if(!k) d[y]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
}
}
no[x]=i;
return flow-rest;
}
int dinic(){
int ans=0,flow=0;
while(bfs()){
while(flow=dfs(s,INF)) ans+=flow;
}
return ans;
}
int main(){
int a,b,c,d;
cin>>n;
s=n+1,t=s+1;
while(cin>>a>>b>>c>>d){
add(a,b,d-c);
in[b]+=c,out[a]+=c;
}
for(int i=1;i<=n;++i){
if(in[i]>out[i]) add(s,i,in[i]-out[i]);
if(out[i]>in[i]) add(i,t,out[i]-in[i]);
}
add(n,1,INF);
dinic();
int t1=INF-w[co^1];
s=n,t=1,w[co]=0,w[co^1]=0;
int t2=dinic();
cout<<t1-t2;
return 0;
}
字符串
AC 自动机
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
const int N=2e6+5;
struct node{
int end,fail,s[26];
};
node a[N];
int n,co;
void insert(string s){
int u=0;
for(int i=0;i<s.size();++i){
if(!a[u].s[s[i]-'a']) a[u].s[s[i]-'a']=++co;
u=a[u].s[s[i]-'a'];
}
a[u].end++;
}
void get_fail(){
queue<int> q;
for(int i=0;i<26;++i)
if(a[0].s[i])
q.push(a[0].s[i]),a[a[0].s[i]].fail=0;
while(q.size()){
int x=q.front();q.pop();
for(int i=0;i<26;++i){
if(a[x].s[i])
a[a[x].s[i]].fail=a[a[x].fail].s[i],
q.push(a[x].s[i]);
else a[x].s[i]=a[a[x].fail].s[i];
}
}
}
int fi(string s){
int res=0,u=0;
for(int i=0;i<s.size();++i){
u=a[u].s[s[i]-'a'];
for(int j=u;j && a[j].end!=-1;j=a[j].fail)
res+=a[j].end,a[j].end=-1;
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){string s;cin>>s;insert(s);}
get_fail();
string s;cin>>s;
printf("%d",fi(s));
return 0;
}
数学
动态规划（DP）
基础算法
快速幂
点击查看代码
int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=(res*x)%p;
y>>=1,x=(x*x)%p;
}
return res%p;
}