题解：要求最小化平均割权值，不妨二分最小平均割权值。对于每个二分的权值mid, 边权变为：原来权值-mid,注意题目中割集与网络流中定义的不同，如果边权为负则将该边加入答案，最后跑最大流，如果最大流的值加负权边值小于0则可以缩小枚举值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=110,M=1e3,inf=1e9; 4 int h[N],e[M],w[M],ne[M],idx; 5 double f[M]; 6 int d[N],cur[N]; 7 int n,m,S,T; 8 void add(int a,int b,int c) 9 { 10 ne[idx]=h[a],w[idx]=c,e[idx]=b,h[a]=idx++; 11 ne[idx]=h[b],w[idx]=c,e[idx]=a,h[b]=idx++; 12 } 13 bool bfs() 14 { 15 memset(d,-1,sizeof d); 16 queue<int>q; 17 q.push(S); 18 d[S]=0; 19 cur[S]=h[S]; 20 while(q.size()) 21 { 22 int t=q.front(); 23 q.pop(); 24 for(int i=h[t];i!=-1;i=ne[i]) 25 { 26 int j=e[i]; 27 if(d[j]==-1&&f[i]>0) 28 { 29 d[j]=d[t]+1; 30 cur[j]=h[j]; 31 if(j==T)return true; 32 q.push(j); 33 } 34 } 35 } 36 return false; 37 } 38 double find(int u,double limit) 39 { 40 if(u==T)return limit; 41 double flow=0; 42 for(int i=cur[u];i!=-1&&flow<limit;i=ne[i]) 43 { 44 int j=e[i]; 45 cur[j]=h[j]; 46 if(d[j]==d[u]+1&&f[i]>0) 47 { 48 double t=find(j,min(f[i],limit-flow)); 49 if(!t)d[j]=-1; 50 f[i]-=t,f[i^1]+=t,flow+=t; 51 } 52 } 53 return flow; 54 } 55 double dinic(double mid) 56 { 57 double res=0; 58 for(int i=0;i<idx;i+=2) 59 { 60 if(w[i]<=mid) 61 { 62 res+=w[i]-mid; 63 f[i]=f[i^1]=0; 64 } 65 else f[i]=f[i^1]=w[i]-mid; 66 } 67 double r=0,flow; 68 while(bfs())while(flow=find(S,inf))r+=flow; 69 return r+res; 70 } 71 int main() 72 { 73 memset(h,-1,sizeof h); 74 cin>>n>>m>>S>>T; 75 while(m--) 76 { 77 int a,b,c; 78 scanf("%d%d%d",&a,&b,&c); 79 add(a,b,c); 80 } 81 double l=0,r=1e7; 82 while(r-l>1e-4) 83 { 84 double mid=(l+r)/2; 85 if(dinic(mid)<0)r=mid; 86 else l=mid; 87 } 88 printf("%.2lf",r); 89 }