1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define N 1008  6 #define M 1000009  7 #define eps 0.00001  8 using namespace std;  9 int S,T,A[N],B[N],f[N][N],n,m,cnt=1,tot,head[N],next[M],u[M],d[N],q[N]; 10 double v[M],sum; 11 void jia1(int a1,int a2,double a3) 12 { 13     cnt++; 14     next[cnt]=head[a1]; 15     head[a1]=cnt; 16     u[cnt]=a2; 17     v[cnt]=a3; 18     return; 19 } 20 void jia(int a1,int a2,double a3) 21 { 22     jia1(a1,a2,a3); 23     jia1(a2,a1,0); 24     return; 25 } 26 bool bfs() 27 { 28     memset(d,0,sizeof(d)); 29     int h=0,t=1; 30     q[1]=S; 31     d[S]=1; 32     for(;h
         
          eps;) 96       { 97         double mid=(l+r)/2.0; 98         jian(mid); 99         double ans=0;100         for(;bfs();)101           ans+=dinic(S,0x7fffffff);102         if(ans>=(sum-eps))103           {104             qq=mid;105             r=mid;106           }107         else108           l=mid;109       }110     printf("%.6lf\n",qq);111     return 0;112 }
         
        
       
      
     

二分答案网络流。