1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 10000 5 #define inf 2139062143 6 using namespace std; 7 int cnt=1,n,m,T,d[M],q[2*M],f[M],head[M],next[10*M],u[10*M],v[10*M],w[10*M],fro[10*M],fr[M]; 8 int mp[100][100]; 9 int ans;10 void jia1(int a1,int a2,int a3,int a4)11 {12     cnt++;13     next[cnt]=head[a1];14     head[a1]=cnt;15     fro[cnt]=a1;16     u[cnt]=a2;17     v[cnt]=a3;18     w[cnt]=a4;19 }20 void jia(int a1,int a2,int a3,int a4)21 {22     jia1(a1,a2,a3,a4);23     jia1(a2,a1,0,-a4);24     return;25 }26 bool spfa()27 {28     memset(d,127,sizeof(int)*(T+1));29     d[0]=0;30     f[0]=1;31     q[1]=0;32     int h=0,t=1;33     for(;h
        
         d[p]+w[i])40             {41                 d[u[i]]=d[p]+w[i];42                 fr[u[i]]=i;43                 if(!f[u[i]])44                   {45                     f[u[i]]=1;46                     t++;47                     q[t]=u[i];48                     }49             }50       }51     if(d[T]!=inf)52       return 1;53     return 0;54 }55 void mcf()56 {57     int mx=inf;58     for(int i=fr[T];i;i=fr[fro[i]])59       mx=min(mx,v[i]);60     for(int i=fr[T];i;i=fr[fro[i]])61       {62         v[i]-=mx;63         v[i^1]+=mx;64         ans+=mx*w[i];65       }66     return;67 }68 int main()69 {70     scanf("%d%d",&n,&m);71     T=m+m*n+1;72     for(int i=1;i<=m;i++)73       jia(0,i,1,0);74     for(int i=1;i<=m;i++)75       for(int j=1;j<=n;j++)76         scanf("%d",&mp[i][j]);77     for(int i=1;i<=m;i++)78       for(int j=1;j<=n;j++)79         for(int k=1;k<=m;k++)80           jia(i,(j-1)*m+k+m,1,mp[i][j]*k);81     for(int i=1;i<=n;i++)82       for(int j=1;j<=m;j++)83         jia((i-1)*m+j+m,T,1,0);84     for(;spfa();)85       mcf();86     printf("%.2lf\n",ans/(m*1.0));87     return 0;88 }
        
       
      
     

拆点网络流，将每个技术人员拆成顾客数个，分别代表倒数第一个修，倒数第二个修，。。。。；顾客向他们连边权值为他及以后的他消耗的等待时间。