1. 题目

传送门=￣ω￣=

大意：有 $N$个车主，每个车主有 1 辆车，他们在同一时刻要修车。有 $M$个修车的。给出 “第 i 个车给第 j 个修车的要修多久”。求车主的平均等待时间。等待时间指的是一个车主从开始时刻到自己的车子被修完所用的时间。

2. 题解

设第 $i$辆车给第 $j$个修车的修所用的时间为 $t(i,j)$。

把每个修车的拆 (shui) 成 (jie)$n×m$个点，点 $(i,j)$表示第 $i$个修车的修倒数第 $j$辆车。

然后每个车作为一个点，连边到每个修车的拆成的点上。设当前是第 $i$辆车，连边到点 $(j,k)$上。则边的流量为 1，权值为 $t(i,j)×k$。

这样就构成了一个二分图了。

为什么这么构图呢？因为这样我们枚举了每种可能的情况：每辆车给谁修还有那辆车先修。而且不难发现，修当前车子的时候不会对之前修好的车产生影响，只会对后面再来修的车产生影响。所以让 $j$修当前这辆车 $i$造成的影响就是后面修的每辆车都增加了 $t(i,j)$。

因此。。。就是这么搞的。

代码：

#include <bits/stdc++.h>
#define NS (2000)
#define MS (80000)
using namespace std;
const int T=1001;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct edge{int u,v,d,c;}e[MS];
int m,n,t[100][100],head[NS],nxt[MS],to[MS],cnt,dis[NS],vis[NS],ans;
bool book[NS];
queue<int> que;
inline void push(int a,int b){nxt[cnt]=head[a],to[cnt]=b,head[a]=cnt++;}
inline void add(int a,int b,int c)
{
    e[cnt].u=a,e[cnt].v=b,e[cnt].d=c,e[cnt].c=1;
    push(a,cnt),e[cnt]=e[cnt-1],swap(e[cnt].u,e[cnt].v);
    e[cnt].d=-c,e[cnt].c=0,push(b,cnt);
}
inline bool spfa()
{
    memset(dis,127,sizeof(dis)),dis[0]=0,que.push(0),book[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop(),book[F]=0;
        for(int i=head[F];i!=-1;i=nxt[i])if(e[to[i]].c)
            if(dis[e[to[i]].v]>dis[F]+e[to[i]].d)
            {
                dis[e[to[i]].v]=dis[F]+e[to[i]].d,vis[e[to[i]].v]=to[i];
                if(!book[e[to[i]].v])que.push(e[to[i]].v),book[e[to[i]].v]=1;
            }
    }
    return (dis[T]<2e9);
}
int main()
{
    IN(m),IN(n),memset(head,-1,sizeof(head)),vis[0]=-1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)IN(t[i][j]);
    for(int i=1;i<=m*n;i++)add(0,i,0);
    for(int i=m*n+1;i<=m*n+n;i++)add(i,T,0);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                add((i-1)*n+j,m*n+k,t[k][i]*j);
    while(spfa())
        for(int i=vis[T];i!=-1;i=vis[e[i].u])e[i].c=0,e[i^1].c=1,ans+=e[i].d;
    printf("%.2f\n",(double)ans/(double)n);
    return 0;
}