题目大意是给一张网络，网络可能存在不同边集的最小割，求出拥有最少边集的最小割，最少的边是多少条?
思路：题目很好理解，就是找一个边集最少的最小割，一个方法是在建图的时候把边的容量处理成C *（E+1 )+1,C是初始容量，E是边的个数，假设之前不做此操作处理求得最大流是maxf，处理之后跑dinic求出的最大流就是 maxf *（E+1）+ n , n就代表用了几条边，其中 n 必定是小于 E+1的，这样把处理之后的最大流模上（E+1）得到n，其中n就是最小割的边数，因为每用到一条边得到的最大流就会+1，那么+n就是用了n条边，这个n就是最少边集的个数。
AC 代码:
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 205;
const int MAX = 0x3f3f3f3f;
struct node{
vector<int> vex;//某个节点连接的点
vector<int> num;//连接节点边的序号
}g[maxn];
struct edge{
int u,v,c;
}e[maxn*maxn];
int edgenum,sp,tp;
int d[maxn];
void addedge(int u,int v,int c){
e[edgenum].u = u;
e[edgenum].v = v;
e[edgenum].c = c;
g[u].vex.push_back(v),g[u].num.push_back(edgenum++);
// 建立双向边操作
e[edgenum].u = v;
e[edgenum].v = u;
e[edgenum].c = 0;
g[v].num.push_back(edgenum++),g[v].vex.push_back(u);
}
int bfs(){
memset(d,-1,sizeof(d));
queue<int> q;
q.push(sp);
d[sp] = 0;
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = 0;i<g[now].vex.size() ;i++ ){
int tv = g[now].vex[i];
int te = g[now].num[i];
if(e[te].c > 0 && d[tv] == -1){
d[tv] = d[now] + 1;//增加深度
q.push(tv);
}
}
}
return d[tp]!=-1;
}
int dfs(int a,int b){
int r = 0;
if(a == tp){
return b;
}
for(int i = 0;i<g[a].num.size()&& r<b ;i++ ){
int tv = g[a].vex[i];
int te = g[a].num[i];
if(e[te].c > 0 && d[tv] == d[a] + 1){
int tc = min(e[te].c ,b - r);//求出可以流过的流量
tc = dfs(tv,tc);//递归寻找增广路
r+=tc;
e[te].c-=tc;
e[te^1].c+=tc;
}
}
if(!r){
d[a] = -2;
}
return r;
}
int dinic(){
int total = 0;
while(bfs()){
while(1){
int t = dfs(sp,MAX);
if(!t){//找不到增广路，t=0，循环终止
break;
}
total+=t;
}
}
return total;
}
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
cin>>sp>>tp;
edgenum = 0;
for(int i = 0;i<maxn;i++){
g[i].num.clear() ,g[i].vex.clear() ;
}
for(int i = 0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
addedge(u,v,w*(m+1)+1); //边容量扩大
}
int ans = dinic();
cout<<ans%(m+1)<<endl;
}
return 0;
}