注：此浅谈中借用了一些博客和课件中的理论，模型描述。
最小割问题是指：给出一种有向图（无向图）和两个点$S$、$T$，以及图中的边的边权，求一个权值和最小的边集，使得删除这些边之后，$S$和$T$不连通。这类问题，一般运用最大流等于最小流定理，求出$S$到$T$的最大流来解决。
例题一：[bzoj2521 [Shoi2010]最小生成树]
分析与题解：题目中所说的操作——对于一条边，我们将其不变，其他的边减一。在做题的时候不太方便，所以我们将其进行转化，我们把这个操作转换成为：对于当前边，我们将其加一，其他的边不变。这样我们做题就方便多了。
考虑最小生成树的求法：$kruskal$，要想让指定边一定出现在最小生成树中，我们就要让边权小于等于指定边的所有边都加入到图中之后，指定边的两个端点依旧不连通，这样我们就可以转化问题，并建立模型。我们将边权小于等于指定边的边连到图中，并以指定边的两个端点为$S$和$T$求最小割。我们所连的边权并不是原图中的边权，因为我们在这里要求的代价最小，所以我们的每一个边的边权要改为代价。因为我们如果要使当前边不出现在图中，我们就要让他的边权在一通操作之后大于指定变边，所以一个边的代价为$d_i-d_{lab}+1$。
#include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 1000 #define inf 1000000000 int n,m,lab,s,t,dis[N],ans,a[N],b[N],c[N]; int cur[N],head[N],to[N<<5],nxt[N<<5],val[N<<5],idx=1; void add(int a,int b,int c) {nxt[++idx]=head[a],to[idx]=b,val[idx]=c,head[a]=idx;} bool bfs() { memset(dis,-1,sizeof dis); queue <int> q;q.push(s),dis[s]=0; while(!q.empty()) { int p=q.front();q.pop(); if(p==t) return true; for(int i=head[p];i;i=nxt[i]) if(val[i]>0&&dis[to[i]]==-1) dis[to[i]]=dis[p]+1,q.push(to[i]); } return false; } int dfs(int p,int flow) { int now,temp=flow; if(p==t) return flow; for(int i=cur[p];i;i=nxt[i]) if(val[i]>0&&dis[to[i]]==dis[p]+1) { now=dfs(to[i],min(val[i],temp)); if(!now) dis[to[i]]=-1; temp-=now,val[i]-=now,val[i^1]+=now; if(val[i]) cur[p]=i; if(!temp) break; } return flow-temp; } void dinic() {while(bfs()) memcpy(cur,head,sizeof head),ans+=dfs(s,inf);} int main() { scanf("%d%d%d",&n,&m,&lab); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); s=a[lab],t=b[lab]; for(int i=1;i<=m;i++) if(i!=lab&&c[i]<=c[lab]) add(a[i],b[i],-c[i]+c[lab]+1),add(b[i],a[i],-c[i]+c[lab]+1); dinic(),printf("%d\n",ans); }