P2053 [SCOI2007]修车

分析：

最小平均等待时间，即总最短等待时间，设一个技术人员依次维修了 t1~tk k 辆车，则它对总等待时间的贡献是： $t1*k+t2*(k-1)+...+tk*1$t1∗k+t2∗(k−1)+...+tk∗1 那么把每个技术人员分成 n 个时间段，第 i 个时间段的贡献即： $(n-i+1)*ti$(n−i+1)∗ti这样一共有 n*m 个新技术人员了，与 n 辆车所代表的点构成完全二分图，创建源点和汇点，跑一遍最大流最小费用即可。

代码：

#include<bits/stdc++.h>

#define rg register
#define I inline
using namespace std;

I int rd(){
    int x=0,f=0; char c=getchar();
    while(c<'0'||c>'9'){f|=c=='-';c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
    return f?-x:x;
}

const int N = 1000+10;
const int M = 1E5+10;
const int INF = 1E9;

int lnk[N],ter[M],nxt[M],cap[M],cost[M],tot=1;
int n,m,cur[N],dis[N];
bool vis[N];

I void add(int u,int v,int w,int c){
    ter[++tot] = v,
      nxt[tot] = lnk[u],
      cap[tot] = w, 
     cost[tot] = c,
	    lnk[u] = tot;
}
I void addedge(int u,int v,int w,int c){   
    add(u,v,w, c), 
    add(v,u,0,-c);
}

int q[M],ANS,RET,S,T;

I bool spfa(){
	for(rg int i=0;i<=T;i++) dis[i]=INF,vis[i]=0;
  

    int l=0,r=0;q[0]=S;
    dis[S]=0,vis[S]=1;
    
    while(l<=r)
	{
        int u=q[l++]; vis[u]=0;
        for (rg int i=lnk[u];i;i=nxt[i]){
            int v=ter[i];
            if(cap[i]&&dis[v]>dis[u]+cost[i])
			{
                dis[v]=dis[u]+cost[i];
                if(!vis[v]) q[++r]=v,vis[v]=1;
            }
        }
    }
    return dis[T]!=INF;
}

I int dfs(int u,int flow){
    if(u==T)
    {
        ANS+=flow;
	    RET+=flow*dis[T];
	    return flow; 
    }
    vis[u]=1;
    int ans=0;
    for(rg int &i=cur[u];i;i=nxt[i])
	{
        int v=ter[i]; if(vis[v]) continue;
        if(cap[i]&&dis[v]==dis[u]+cost[i]){
            int x=dfs(v,min(cap[i],flow));
            ans+=x,cap[i^1]+=x,cap[i]-=x,flow-=x;
            if(!flow) break;
        }
    }
    vis[u]=0;
    return ans;
}

I void mcmf(){
    while(spfa()){
        for(rg int i=0;i<=T;i++) cur[i]=lnk[i];
        dfs(S,INF);
    }
}

int t[100][15];

int main() {
    m=rd(),n=rd();
    for(rg int i=1;i<=n;i++)
        for(rg int j=1;j<=m;j++)
            t[i][j]=rd();
    
	S=0,T=n+m*n+1;
	for(rg int i=1;i<=n;i++) addedge(0,i,1,0);
	for(rg int i=1;i<=n;i++)
	    for(rg int j=1;j<=m;j++)
	    {
	    	for(rg int z=1;z<=n;z++)
			{
				addedge(i,n+n*(j-1)+z,1,t[i][j]*z);
			}
		}
	for(int i=1;i<=n*m;i++) addedge(i+n,T,1,0); 
    mcmf();
    printf("%.2lf",1.0*RET/n);
    return 0;
}