一、题目描述：
n 个点，m 条边，带边权。起点为 1，终点为 n。
求最小割以及在最小割的情况下的最少割的边数。
2<=n<=32,1<=m<=1e3。
二、解题思路：
第一问很好求解，直接最大流即可。
第二问想不出来，看了题解把我震惊了！
设边 i 原本的边权为 w[i]，现在我们令新边权 v[i]=w[i]*2e3 +1。
设跑出来最大流为ans，割了k条边，编号为 $a_1$,$a_2$,...,$a_k$。
所以 ans={$\sum_{i=1}^{n} w[a_i]$}*1e3+k，已知 k<=m<2e3
那么有 ans/2e3=$\sum_{i=1}^{n} w[a_i]$，ans%1e3=k。
所以第一问答案为 ans/2e3，第二问答案为 ans%2e3。
这个题可能有重边。用一个 p[i][j] 表示 i 到 j 的边权比较保险。
算法 EK，时间复杂度最差 O(n$m^2$)，但实际上跑的飞快。
三、完整代码：
#include<iostream> #define N 50 #define M 1010 #define ll long long using namespace std; ll n,m,l,r,u1,v1,w1,ans; ll q[N],w[N],vis[N],pre[N],p[N][N]; struct EDGE{ ll v,nxt; }edge[M*2]; ll head[N],cnt=-1; void add(ll u,ll v) { edge[++cnt].v=v; edge[cnt].nxt=head[u]; head[u]=cnt; } bool bfs() { for(ll i=1;i<=n;i++) vis[i]=0; l=r=1,q[1]=1; while(l<=r) { ll u=q[l]; l++; if(u==n) return true; for(ll i=head[u];i!=-1;i=edge[i].nxt) { ll to=edge[i].v; if(!vis[to]&&p[u][to]>0) { vis[to]=1; pre[to]=u; q[++r]=to; w[to]=min(w[u],p[u][to]); } } } return false; } void Edmonds_Karp() { w[1]=1e18; while(bfs()) { ll u=n; ans+=w[n]; while(u!=1) { p[u][pre[u]]+=w[n]; p[pre[u]][u]-=w[n]; u=pre[u]; } } } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(ll i=1;i<=n;i++) head[i]=-1; for(ll i=1;i<=m;i++) { cin>>u1>>v1>>w1; p[u1][v1]+=w1*M+1; add(v1,u1);add(u1,v1); } Edmonds_Karp(); cout<<ans/M<<" "<<ans%M<<'\n'; return 0; }
四、写题心得：
感觉网络流的题都要有一个特别妙的构思才行。不过这个题做了也真的蛮有收获的。加油！拜拜！