求最小的割点数
将点拆成两个点，加入额外的边来约束，\(x \to x‘\) 流量为 1 的边
- 最大流等于最小割
证明
考虑跑完最大流的图，无法找到从 \(S\) 到 \(T\) 通路，也就是说图被满流的边分成了两部分，连接两个部分的边就是最小割，且他们的权值加起来就是最大流
从最小割的角度来看，一但割去的边 \(<\) 最大流，那一定可以找到 \(S\) 到 \(T\) 的通路
#include<bits/stdc++.h>
using namespace std;
#define rg register
inline int read(){
rg char ch=getchar();
rg int x=0,f=0;
while(!isdigit(ch)) f|=(ch==‘-‘),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int n,m,s,t;
int head[100010],ver[100010],nxt[100010],flow[100010],hh[100010],tot=1;
int dis[100010],ans;
const int inf=99999999;
inline void add(int x,int y,int z){
ver[++tot]=y;
flow[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
int bfs(){
for(int i=0;i<=(n<<1);++i) hh[i]=head[i];
queue<int> q;
q.push(s);
memset(dis,-1,sizeof dis);
dis[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int y,i=head[x];i;i=nxt[i]){
y=ver[i];
if(dis[y]==-1&&flow[i]){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return dis[t]==-1?false:true;
}
int dfs(int x,int f){
if(x==t||!f)return f;
int used=0;
for(int w,y,&i=hh[x];i;i=nxt[i]){
y=ver[i];
if(dis[y]==dis[x]+1&&flow[i]){
w=dfs(y,min(f-used,flow[i]));
if(w){
flow[i]-=w;
flow[i^1]+=w;
used+=w;
if(used==f) return f;
}
}
}
return used;
}
inline void dinic(){
while(bfs()) ans+=dfs(s,99999999);
}
int main(){
n=read(),m=read(),s=read()+n,t=read();
for(int i=1;i<=n;++i) add(i,i+n,1),add(i+n,i,0);
for(int x,y,i=1;i<=m;++i){
x=read(),y=read();
add(x+n,y,inf);
add(y,x+n,0);
add(y+n,x,inf);
add(x,y+n,0);
}
dinic();
printf("%d",ans);
return 0;
}