一、图论
1.单源最短路
(1)spfa
已加SLF优化 419ms
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e4+,M=5e5+,INF=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,s,u,v,w;
struct edge{
int v,ne,w;
}e[M<<];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}
int d[N],q[N],head,tail,inq[N];
void spfa(int s){
for(int i=;i<=n;i++) d[i]=INF;
head=tail=;
q[tail++]=s;inq[s]=;d[s]=;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;
else q[tail++]=v,lop(tail);
inq[v]=;
}
}
}
}
}
int main(){
n=read();m=read();s=read();
for(int i=;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}
spfa(s);
for(int i=;i<=n;i++) printf("%d ",d[i]);
}
(2)dijkstra 503ms
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e4+,M=5e5+,INF=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n,m,s,u,v,w;
struct edge{
int v,ne,w;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
struct hn{
int u,d;
hn(int a=,int b=):u(a),d(b){}
bool operator <(const hn &r)const{return d>r.d;}
};
priority_queue<hn> q;
int d[N],done[N];
void dij(int s){
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
q.push(hn(s,));
while(!q.empty()){
hn x=q.top();q.pop();
int u=x.u;if(done[u]) continue;
done[u]=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!done[v]) q.push(hn(v,d[v]));//xiao you hua
}
}
}
}
int main(){
n=read();m=read();s=read();
for(int i=;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}
dij(s);
for(int i=;i<=n;i++) printf("%d ",d[i]);
}
(3)dijkstra+配对堆 380ms 吊打用SLF优化的spfa啊啊啊啊啊
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
#define pa pair<int,int>
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pa,greater<pa>,thin > heap;
const int N=1e4+,M=5e5+,INF=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,s,u,v,w;
struct edge{
int v,ne,w;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
} heap q;
heap::point_iterator it[N];
int d[N];
void dij(int s){
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
it[s]=q.push(mp(,s));
while(!q.empty()){
int u=q.top().second;q.pop();
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(it[v]!=) q.modify(it[v],mp(d[v],v));
else it[v]=q.push(mp(d[v],v));
}
}
}
}
int main(){
n=read();m=read();s=read();
for(int i=;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}
dij(s);
for(int i=;i<=n;i++) printf("%d ",d[i]);
}
2.判负环
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e3+,M=1e5+,INF=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,s,u,v,w;
struct edge{
int v,ne,w;
}e[M+N];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
inline void lop(int &x){x++;if(x==N) x=;}
int q[N],head=,tail=,inq[N];
int d[N],nc[N];
bool spfa(int s){
head=tail=;
for(int i=;i<=n;i++) d[i]=INF,inq[i]=nc[i]=;
q[tail]=s;inq[s]=nc[s]=; lop(tail);
d[s]=;
while(head!=tail){
int u=q[head];inq[u]=; lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
inq[v]=;q[tail]=v; lop(tail);
if(++nc[v]>n) return false;
}
}
}
}
return true;
}
int main(){
n=read();m=read();s=read();
for(int i=;i<=m;i++){
u=read();v=read();w=read();
if(u==v&&w<) {printf("-1");return ;}
if(u!=v)ins(u,v,w);
} int ss=n+;//超级源
for(int i=;i<=n;i++) ins(ss,i,);
int flag=spfa(ss);
if(!flag){printf("-1");return ;}
spfa(s);
for(int i=;i<=n;i++){
if(d[i]>=INF) printf("NoPath\n");
else printf("%d\n",d[i]);
}
}
3.最小生成树
kruskal
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=,M=2e5+,INF=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v,w;
int cnt=;
struct edge{
int u,v,w;
bool operator <(const edge &r)const{return w<r.w;}
}e[M];
int fa[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int kruskal(){
int ans=,cnt=;
for(int i=;i<=n;i++) fa[i]=i;
sort(e+,e++m);
for(int i=;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int f1=find(u),f2=find(v);
if(f1!=f2){
ans+=w;
fa[f1]=f2;
cnt++;
if(cnt==n-) break;
}
}
return ans;
}
int main(){
n=read();m=read();
for(int i=;i<=m;i++){
e[i].u=read();e[i].v=read();e[i].w=read();
}
int ans=kruskal();
printf("%d",ans);
}
4.floyd
(1)传递闭包
d[i][j]=d[i][j]||(d[i][k]&&d[k][j])
(2)最小环
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=,M=1e4+,INF=1e8+;//1E9+1E9+1E9溢出
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v,w,g[N][N];
int d[N][N],ans=INF;
void floyd(){
ans=INF;
for(int k=;k<=n;k++){
for(int i=;i<=k-;i++)
for(int j=i+;j<=k-;j++)
ans=min(ans,g[i][k]+g[k][j]+d[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
} }
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++) for(int j=i+;j<=n;j++) d[i][j]=d[j][i]=g[i][j]=g[j][i]=INF;
for(int i=;i<=m;i++){
u=read();v=read();w=read();
d[u][v]=d[v][u]=g[u][v]=g[v][u]=w;
}
floyd();
if(ans==INF) puts("No solution.");
else printf("%d\n",ans);
}
}
5.割点
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+,M=1e5+,INF=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n=,m,u,v;
struct edge{
int v,ne;
}e[M<<];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
int dfn[N],low[N],dfc=,iscut[N];
void dfs(int u,int fa){
dfn[u]=low[u]=++dfc;
int child=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!dfn[v]){
child++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) iscut[u]=;
}else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
if(fa==&&child==) iscut[u]=;
}
int main(){
n=read();m=read();
for(int i=;i<=m;i++){u=read();v=read();ins(u,v);}
for(int i=;i<=n;i++) if(!dfn[i]) dfs(i,); int ans=;
for(int i=;i<=n;i++) if(iscut[i]) ans++;
printf("%d\n",ans);
for(int i=;i<=n;i++) if(iscut[i]) printf("%d ",i);
}
6.tarjan 强连通分量
POJ2186
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e4+,M=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v;
struct edge{
int v,ne;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int dfn[N],belong[N],low[N],dfc,scc,st[N],top;
int size[N];
void dfs(int u){
dfn[u]=low[u]=++dfc;
st[++top]=u;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!belong[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
scc++;
while(true){
int x=st[top--];
belong[x]=scc;
size[scc]++;
if(x==u) break;
}
}
}
int outd[N],ind[N],ans;
void point(){
for(int u=;u<=n;u++)
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(belong[u]!=belong[v]) outd[belong[u]]++,ind[belong[v]]++;
}
}
int main(){
n=read();m=read();
for(int i=;i<=m;i++){u=read();v=read();ins(u,v);}
for(int i=;i<=n;i++) if(!dfn[i]) dfs(i);
point();
for(int i=;i<=scc;i++){
if(outd[i]==){
if(ans){ans=;break;}
else ans=size[i];
}
}
printf("%d",ans);
}
7.二分图染色
bool color(int u,int c){
col[u]=c;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(col[u]==col[v]) return false;
if(!col[v]&&!color(v,-c)) return false;
}
return true;
}
8.二分图最大匹配
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,s,u,v;
struct edge{
int v,ne;
}e[N*N<<];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int vis[N],le[N];
bool find(int u){
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!vis[v]){
vis[v]=;
if(!le[v]||find(le[v])){
le[v]=u;
return true;
}
}
}
return false;
}
int ans=;
void hungary(){
for(int i=;i<=n;i++){
memset(vis,,sizeof(vis));
if(find(i)) ans++;
}
}
int main(){
n=read();m=read();int t=read();
for(int i=;i<=t;i++){u=read();v=read();if(v>m)continue;ins(u,v);}
ans=;
hungary();
printf("%d\n",ans);
}
9、tarjan缩点
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 10005
#define M 100005
#define INF 1e9
using namespace std;
int tot,nxt[M],point[N],v[M],low[N],Dfn[N],nn,cnt,a[N],c[N],x[M],y[M];
int tot1,nxt1[M],point1[N],v1[M],f[N],out[N],stack[N],num,belong[N],ans;
bool vis[N];
void addline(int x,int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}
void addline1(int x,int y){++tot1; nxt1[tot1]=point1[x]; point1[x]=tot1; v1[tot1]=y;}
void tarjan(int x)
{
Dfn[x]=low[x]=++nn; vis[x]=; stack[++cnt]=x;
for (int i=point[x];i;i=nxt[i])
if (!Dfn[v[i]])
{
tarjan(v[i]);
low[x]=min(low[x],low[v[i]]);
}
else if (vis[v[i]]) low[x]=min(low[x],Dfn[v[i]]); if (low[x]==Dfn[x])
{
num++;
while (stack[cnt]!=x)
{
c[num]+=a[stack[cnt]];
belong[stack[cnt]]=num;
vis[stack[cnt]]=;
cnt--;
}
c[num]+=a[stack[cnt]];
belong[stack[cnt]]=num;
vis[stack[cnt]]=;
cnt--;
}
}
void dp(int x,int fa)
{
if (vis[x]) return;
f[x]=c[x];vis[x]=;int maxx=;
for (int i=point1[x];i;i=nxt1[i])
if (v1[i]!=fa)
{
dp(v1[i],x);
maxx=max(maxx,f[v1[i]]);
}
f[x]+=maxx;
}
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
for (i=;i<=n;i++) scanf("%d",&a[i]);
for (i=;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
addline(x[i],y[i]);
}
for(i=;i<=n;i++)
if(!Dfn[i])tarjan(i);
for(i=;i<=m;i++)
if(belong[x[i]]!=belong[y[i]])
addline1(belong[x[i]],belong[y[i]]);
ans=-INF;
memset(vis,,sizeof(vis));
for(i=;i<=num;i++)
if(!vis[i])dp(i,),ans=max(ans,f[i]);
printf("%d",ans);
}
数据结构
1.st表
int a[N],f[N][];
void init(int n){
for(int i=;i<=n;i++) f[i][]=a[i];
for(int j=;j<=;j++)
for(int i=;i+(<<j)-<=n;i++)
f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
}
int RMQ(int l,int r){
int k=log(r-l+)/log(); //2^k<=l~r
return min(f[l][k],f[r-(<<k)+][k]);
}
2.trie树
int ch[N*L][],size=,val[N*L];
void insert(char s[],int n,int id){
int u=;
for(int i=;i<=n;i++){
int v=s[i]-'a';
if(!ch[u][v]) ch[u][v]=++size;
u=ch[u][v];
}
val[u]=id;//printf("ins %d %d\n",u,id);
}
3.单调栈
求最大全flag子矩阵
void sol(int flag){
memset(tot,,sizeof(tot));
for(int i=;i<=n;i++){
top=;
for(int j=;j<=m;j++){
if(a[i][j]==flag) tot[j]++;
else tot[j]=;
data t;
t.h=tot[j];t.l=;t.pos=j;
while(top&&st[top].h>=t.h){
int l=st[top].l+j--st[top].pos,h=st[top].h;
ans1=max(ans1,min(l,h)*min(l,h));
ans2=max(ans2,l*h);
t.l+=st[top].l;
top--;
}
st[++top]=t;
}
while(top){
int l=st[top].l+m-st[top].pos,h=st[top].h;
ans1=max(ans1,min(l,h)*min(l,h));
ans2=max(ans2,l*h);
top--;
}
}
}
4.单调队列
q[]保存的是下标
//删除
while(head<=tail&&q[head]<=i-k) head++; //也可能< //插入
while(head<=tail&&a[q[tail]]>a[i]) tail--;//单增
q[++tail]=i;
5.并查集
带权
for(int i=;i<=n;i++) fa[i]=i,d[i]=,s[i]=; int fa[N],d[N],s[N];
inline int find(int x){
if(x==fa[x]) return x;
int root=find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}
6.树状数组
模板 int lowbit(int x)
{
return x & (-x);
}
void modify(int x,int add)//一维
{
while(x<=MAXN)
{
a[x]+=add;
x+=lowbit(x);
}
}
int get_sum(int x)
{
int ret=;
while(x!=)
{
ret+=a[x];
x-=lowbit(x);
}
return ret;
}
void modify(int x,int y,int data)//二维
{
for(int i=x;i<MAXN;i+=lowbit(i))
for(int j=y;j<MAXN;j+=lowbit(j))
a[i][j]+=data;
}
int get_sum(int x,int y)
{
int res=;
for(int i=x;i>;i-=lowbit(i))
for(int j=y;j>;j-=lowbit(j))
res+=a[i][j];
return res;
}
7.线段树
//下面是某线段树模板题的代码：
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long LL;
static const int maxm=1e6+;
LL tree[maxm],lazy[maxm],A[maxm],left[maxm],right[maxm];
int n,m; void build(int num,int l,int r){
left[num]=l;right[num]=r;
int mid=(l+r)>>;
if(l==r){ tree[num]=A[l]; return; }
build(num<<,l,mid);
build(num<<|,mid+,r);
tree[num]=tree[num<<]+tree[num<<|];
} void pushdown(int num){
if(lazy[num]){
int mid=(left[num]+right[num])>>;
tree[num<<]+=(mid-left[num]+)*lazy[num];
tree[num<<|]+=(right[num]-mid)*lazy[num];
lazy[num<<]+=lazy[num];
lazy[num<<|]+=lazy[num];
lazy[num]=;
}
} void update(int num,int l,int r,LL add){
if(left[num]>=l&&right[num]<=r){
tree[num]+=(right[num]-left[num]+)*add;
lazy[num]+=add;
return;
}
if(left[num]>r||right[num]<l)return;
pushdown(num);
update(num<<,l,r,add);
update(num<<|,l,r,add);
tree[num]=tree[num<<]+tree[num<<|];
} LL Query(int num,int l,int r){
if(left[num]>=l&&right[num]<=r)return tree[num];
if(left[num]>r||right[num]<l) return ;
LL ret=;
pushdown(num);
ret+=Query(num<<,l,r);
ret+=Query(num<<|,l,r);
return ret;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%lld",&A[i]);
build(,,n);
for(int i=;i<=m;i++){
int f,x,y;LL add;
scanf("%d",&f);
switch(f){
case :scanf("%d%d%lld",&x,&y,&add);update(,x,y,add);break;
case :scanf("%d%d",&x,&y);printf("%lld\n",Query(,x,y));break;
default:printf("Orz %%%");break;
}
} return ;
}
//以下是维护序列的代码：(支持乘法运算)
#include <cstdio> typedef long long LL; static const int maxm=; LL A[maxm],pls[maxm<<],mul[maxm<<],tr[maxm<<];
int left[maxm<<],right[maxm<<];
int n,m;
LL MOD; int build(int id,int l,int r){
left[id]=l;right[id]=r;mul[id]=;
if(l==r)return tr[id]=A[l]%MOD,;
int mid=(l+r)>>;
build(id<<,l,mid);
build(id<<|,mid+,r);
tr[id]=(tr[id<<]+tr[id<<|])%MOD;
} void pushdown(int id){
int l=left[id];int r=right[id];int mid=(l+r)>>;
pls[id<<]=(pls[id<<]*mul[id]%MOD+pls[id])%MOD;
pls[id<<|]=(pls[id<<|]*mul[id]%MOD+pls[id])%MOD;
mul[id<<]=(mul[id]*mul[id<<])%MOD;
mul[id<<|]=(mul[id]*mul[id<<|])%MOD;
tr[id<<]=(tr[id<<]*mul[id]%MOD+pls[id]*(mid-l+)%MOD)%MOD;
tr[id<<|]=(tr[id<<|]*mul[id]%MOD+pls[id]*(r-mid)%MOD)%MOD;
mul[id]=;pls[id]=;
} void modify(int id,int l,int r,int c,int opt){
if(left[id]>=l&&right[id]<=r){
if(opt==){
mul[id]=(mul[id]*c)%MOD;
pls[id]=(pls[id]*c)%MOD;
tr[id]=(tr[id]*c)%MOD;
}else if(opt==){
pls[id]=(pls[id]+c)%MOD;
tr[id]=(tr[id]+(LL)c*(right[id]-left[id]+)%MOD)%MOD;
}
return ;
}
if(right[id]<l||left[id]>r)return ;
pushdown(id);
modify(id<<,l,r,c,opt);
modify(id<<|,l,r,c,opt);
tr[id]=(tr[id<<]+tr[id<<|])%MOD;
} LL Query(int id,int l,int r){
if(left[id]>=l&&right[id]<=r)return tr[id]%MOD;
if(left[id]>r||right[id]<l)return ;
pushdown(id);
return (Query(id<<,l,r)%MOD+Query(id<<|,l,r)%MOD)%MOD;
} int main(){
int opt,l,r,c;
scanf("%d%lld",&n,&MOD);
for(int i=;i<=n;i++)scanf("%lld",&A[i]);
scanf("%d",&m); build(,,n); while(m--){
scanf("%d",&opt);
if(opt!=){
scanf("%d%d%d",&l,&r,&c);
modify(,l,r,c,opt);
}
else scanf("%d%d",&l,&r),printf("%lld\n",Query(,l,r)%MOD);
} return ;
}
8、网络最大流
#include<bits/stdc++.h>
using namespace std;
#define inf 233333333
#define il inline
il int gi()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=a*+x-,x=getchar();
return f?-a:a;
}
const int N=,M=;
struct edge{
int to,net,w;
}e[N*];
int h[M],cnt=,n,m,s,t,ans,flow,dis[M];
queue<int>q;
il void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].w=w,e[cnt].net=h[u],h[u]=cnt;
}
il int bfs()
{
memset(dis,-,sizeof(dis));
dis[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=e[i].net)
{
int v=e[i].to;
if(dis[v]==-&&e[i].w>){dis[v]=dis[u]+;q.push(v);}
}
}
return dis[t]!=-;
}
il int dfs(int u,int op)
{
if(u==t)return op;
int flow=,tmp=;
for(int i=h[u];i;i=e[i].net)
{
int v=e[i].to;
if(dis[v]==dis[u]+&&e[i].w>){
tmp=dfs(v,min(op,e[i].w));
if(!tmp)continue;
op-=tmp;flow+=tmp;
e[i].w-=tmp;e[i^].w+=tmp;
if(!op)break;
// return tmp;
}
}
return flow;
}
int main()
{
n=gi(),m=gi(),s=gi(),t=gi();
int u,v,w;
for(int i=;i<=m;i++)
{
u=gi(),v=gi(),w=gi();
add(u,v,w),add(v,u,);
}
while(bfs())ans+=dfs(s,inf);
printf("%d\n",ans);
return ;
}