Description###

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同

的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最

小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input###

第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人

员维修第i辆车需要用的时间T。

Output###

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

Sample Input###

2 2

3 2

1 4

Sample Output###

1.50

HINT###

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

想法##

这道题还是挺经典的。

我们考虑到每个技术人员那里修车的人等待的总时间，发现那其实就是

于是，我们把每个技术人员拆成n个点，代表某个技术人员修的第几辆车，共mn个点

每个顾客向这mn个点连边，边权为\(t \quad 2t \quad 3t \quad …\)，容量为1

S向每个顾客连容量1费用0的边，那mn个点向T连容量1费用0的边。

跑一遍费用流即可。

代码##

注意：输入时先输m再输n！！！

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

#define INF 2100000000

using namespace std;

const int N = 81+65+81*65;

struct node{

    int v,f,c;

    node *next,*rev;

}pool[N*150],*h[N],*pree[N];

int cnt;

void addedge(int u,int v,int f,int c){

    node *p=&pool[++cnt],*q=&pool[++cnt];

    p->v=v;p->next=h[u];h[u]=p; p->f=f;p->c=c;p->rev=q;

    q->v=u;q->next=h[v];h[v]=q; q->f=0;q->c=-c;q->rev=p;

}

int S,T;

queue<int> que;

int vis[N],d[N],pre[N];

bool spfa(){

    int u,v;

    while(!que.empty()) que.pop();

    for(int i=S;i<=T;i++) d[i]=INF;

    d[S]=0; vis[S]=1; que.push(S);

    while(!que.empty()){

        u=que.front(); que.pop();

        vis[u]=0;

        for(node *p=h[u];p;p=p->next)

            if(p->f && d[v=p->v]>d[u]+p->c){

                d[v]=d[u]+p->c;

                pre[v]=u; pree[v]=p;

                if(!vis[v]) { vis[v]=1; que.push(v); }

            }

    }

    return d[T]!=INF;

}

int MCMF(){

    int f=0,c=0,u,w;

    while(spfa()){

        u=T; w=INF;

        while(u!=S){

            w=min(w,pree[u]->f);

            u=pre[u];

        }

        f+=w; c+=w*d[T];

        u=T;

        while(u!=S){

            pree[u]->f-=w;

            pree[u]->rev->f+=w;

            u=pre[u];

        }

    }

    return c;

}

int n,m;

int main()

{

    int x;

    scanf("%d%d",&m,&n); /**/

    S=0; T=m*n+n+1;

    for(int i=1;i<=n;i++){

        addedge(S,i,1,0);

        for(int j=1;j<=m;j++){

            scanf("%d",&x);

            for(int k=0;k<n;k++)

                addedge(i,n+k*m+j,1,x*(k+1));

        }

    }

    for(int i=1;i<=m;i++)

        for(int k=0;k<n;k++) addedge(n+k*m+i,T,1,0);

    double ans=MCMF();

    printf("%.2lf\n",ans/(double)n);

    return 0;

}