洛谷P1345 无向图最小割点数

题意：

给出一副有$n$个点，$m$条边的无向图，求出这副图的最小割点数

题意：

首先对于有向图，求他的最小割边，只需要令每条边的容量为$1$，求出起点到终点的最大流就是最小割边数了。

容量设为1的原因更多是反映这条路有没有流到达汇点，不需要在乎数量

对无向图，要求其最大流，只需要对双向边都建反向边即可，即

while(m--) {int u,v,w; cin>>u>>v>>w;add(u,v,w);add(v,u,0);add(v,u,w);add(u,v,0);
}

此时要对无向图求最小割点数，考虑将点化成边，这样才符合最大流

考虑将一个点$u$拆分成入点 u 1 u_{1} u1​和出点 u 2 u_{2} u2​，此时同最小割边一样，将这个边权设为$1$，但在拆分源点汇点时，这两个点不可删去，所以内部权值要设为inf

#include<bits/stdc++.h>
using namespace std;using ll=long long;
const int N=2e2+5,M=2e3+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;int ceil(int x,int y) {return x%y?x/y+1:x/y;
}struct way {int to,next,cap;way()=default;way(int to,int next,int cap) {this->to=to;this->next=next;this->cap=cap;}
}edge[M<<2];
int cnt=1,head[N];void add(int u,int v,int cap) {edge[++cnt]=way(v,head[u],cap);head[u]=cnt;
}int n,m,s,t,dis[N],now[N];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 u=q.front();q.pop();for(int i=head[u];i;i=edge[i].next) {auto [v,_,cap]=edge[i];if(dis[v]==inf&&cap) {dis[v]=dis[u]+1;q.push(v); now[v]=head[v];if(v==t) return true;}}}return false;
}int dfs(int u,int flow) {if(u==t) return flow;int ret=0;for(int i=now[u];(now[u]=i);i=edge[i].next) {auto [v,_,cap]=edge[i];if(cap==0||dis[v]!=dis[u]+1) continue;int nflow=dfs(v,min(flow,cap));if(nflow==0) dis[v]=inf;else {edge[i].cap-=nflow;edge[i^1].cap+=nflow;ret+=nflow;flow-=nflow;}}return ret;
}int main() {#ifdef stdjudgefreopen("in.txt","r",stdin);auto TimeFlagFirst=clock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n>>m>>s>>t;for(int i=1;i<=n;i++) {int cap=(i==s||i==t)?inf:1;add(i,i+n,cap);add(i+n,i,0);}while(m--) {int u,v;cin>>u>>v;add(u+n,v,1);add(v,u+n,0);add(v+n,u,1);add(u,v+n,0);}t+=n;n<<=1;int ans=0;while(bfs()) ans+=dfs(s,inf);cout<<ans<<endl;#ifdef stdjudgefreopen("CON","r",stdin);std::cout<<std::endl<<"耗时:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;std::cout<<std::flush;system("pause");#endifreturn 0;
}