同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

　　第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。

　　最小平均等待时间，答案精确到小数点后2位。

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std;10 const int mxn=1010;11 int read(){12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15     return x*f;16 }17 struct edge{18     int u,v,nxt,f,w;19 }e[mxn*100];20 int hd[mxn],mct=1;21 void add_edge(int u,int v,int f,int w){22     e[++mct].v=v;23     e[mct].u=u;24     e[mct].nxt=hd[u];25     e[mct].f=f;e[mct].w=w;26     hd[u]=mct;return;27 }28 void insert(int u,int v,int f,int w){29     add_edge(u,v,f,w); add_edge(v,u,0,-w);return;30 }31 int S,T;32 int dis[mxn],pre[mxn];33 int n,m;34 queue<int>q;35 bool inq[mxn];36 void SPFA(int s){37     memset(dis,0x3f,sizeof dis);38     memset(pre,-1,sizeof pre);39     dis[s]=0;q.push(s);inq[s]=1;40     while(!q.empty()){41         int u=q.front();q.pop();inq[u]=0;42         for(int i=hd[u];i;i=e[i].nxt){43             int v=e[i].v;44             if(e[i].f && dis[v]>dis[u]+e[i].w){45                 dis[v]=dis[u]+e[i].w;46                 pre[v]=i;47                 if(!inq[v]){48                     inq[v]=1;49                     q.push(v);50                 }51             }52         }53     }54     return;55 }56 int mxflow(int s,int t){57     SPFA(s);58     int res=0;59     while(pre[t]!=-1){60         int tmp=0x3f3f3f3f;61         for(int i=pre[t];i!=-1;i=pre[e[i].u]){62             tmp=min(tmp,e[i].f);63         }64         res+=dis[t]*tmp;65         for(int i=pre[t];i!=-1;i=pre[e[i].u]){66             e[i].f-=tmp;67             e[i^1].f+=tmp;68         }69         SPFA(s);70     }71     return res;72 }73 int main(){74     int i,j,w;75     m=read();n=read();76     S=0;T=n+m*n+1;77     for(i=1;i<=n;i++){78         insert(S,i,1,0);79     }80     for(i=1;i<=n;i++){81         for(j=1;j<=m;j++){82             w=read();83             for(int k=1;k<=n;k++){84                 insert(i,j+n+m*(k-1),1,w*k);85             }86         }87     }88     for(i=1;i<=m;i++)89         for(j=1;j<=n;j++)90             insert(i+n+m*(j-1),T,1,0);91     int ans=mxflow(S,T);92 //    printf("!! %d\n",ans);93     printf("%.2f\n",(double)ans/n);94     return 0;95 }

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 using namespace std; 10 const int mxn=1010; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 struct edge{ 18     int u,v,nxt,f,w; 19 }e[mxn*100]; 20 int hd[mxn],mct=1; 21 void add_edge(int u,int v,int f,int w){ 22     e[++mct].v=v; 23     e[mct].u=u; 24     e[mct].nxt=hd[u]; 25     e[mct].f=f;e[mct].w=w; 26     hd[u]=mct;return; 27 } 28 void insert(int u,int v,int f,int w){ 29     add_edge(u,v,f,w); add_edge(v,u,0,-w);return; 30 } 31 int S,T; 32 int dis[mxn],pre[mxn]; 33 int n,m; 34 queue<int>q; 35 bool inq[mxn]; 36 bool mark[mxn]; 37 bool SPFA(int s){ 38     memset(inq,0,sizeof inq); 39     for(int i=0;i<=T;i++)dis[i]=0x3f3f3f3f; 40     dis[T]=0;q.push(T);inq[T]=1; 41     while(!q.empty()){ 42         int u=q.front();q.pop();inq[u]=0; 43         for(int i=hd[u];i;i=e[i].nxt){ 44             int v=e[i].v; 45             if(e[i^1].f && dis[v]>dis[u]-e[i].w){ 46                 dis[v]=dis[u]-e[i].w; 47 //                pre[v]=i; 48                 if(!inq[v]){ 49                     inq[v]=1; 50                     q.push(v); 51                 } 52             } 53         } 54     } 55     if(dis[S]==0x3f3f3f3f)return 0; 56     return 1; 57 } 58 int ans=0; 59 int DFS(int x,int f){ 60     if(x==T){inq[T]=1;return f;} 61     int used=0,w; 62     inq[x]=1; 63     for(int i=hd[x];i;i=e[i].nxt){ 64         int v=e[i].v; 65         if(!inq[v] && e[i].f && dis[x]-e[i].w==dis[v]){ 66             w=f-used; 67             w=DFS(v,min(e[i].f,w)); 68             ans+=w*e[i].w; 69             e[i].f-=w;    e[i^1].f+=w; 70             used+=w; 71             if(used==f)return f; 72         } 73     } 74     return used; 75 } 76  77 void mxflow(int s,int t){ 78     while(SPFA(s)){ 79         inq[T]=1; 80         while(inq[T]){ 81             memset(inq,0,sizeof inq); 82             DFS(S,0x3f3f3f3f); 83         } 84     } 85     return; 86 } 87 int main(){ 88     int i,j,w; 89     m=read();n=read(); 90     S=0;T=n+m*n+1; 91     for(i=1;i<=n;i++){ 92         insert(S,i,1,0); 93     } 94     for(i=1;i<=n;i++){ 95         for(j=1;j<=m;j++){ 96             w=read(); 97             for(int k=1;k<=n;k++){ 98                 insert(i,j+n+m*(k-1),1,w*k); 99             }100         }101     }102     for(i=1;i<=m;i++)103         for(j=1;j<=n;j++)104             insert(i+n+m*(j-1),T,1,0);105     mxflow(S,T);106     printf("%.2f\n",(double)ans/n);107     return 0;108 }