[SCOI2007]修车

# 题意 第$i$个人修第$j$辆车的时间为$t[i,j]$. 现在有$m$个人，$n$辆车，一个人同一时刻只能修一辆车，修一辆车的等待时间是从0时刻到该车修完时的时间。求$n$辆车最小平均等待时间，两位小数输出 $n\leq 60,m\leq 9,t[i,j]\leq 1000$. # 分析 显然转化成最小总时间 假设第$i$个工匠修车的耗时序列是$\{w_1,w_2,\cdots,w_x\}$，其等待总时间表示为 $$ \sum_{i=1}^xw_i(x+1-i) $$ 尝试建模？问题在于$x$不知道怎么搞 因此，我们换一个方式，倒着表示 假设第$i$个工匠修车的耗时序列**倒过来**是$\{w_1,w_2,\cdots,w_x\}$，其等待总时间表示为 $$ \sum_{i=1}^xw_i\times i $$ 也就是说，第$i$辆车，在第$j$个人手中，被放在倒数第$k$个位置，修理的代价为$t[i][j]\times k$. 发现没！$x$参数没了 那么我们希望每一辆车都有人修，而且修车的总代价最小，并且要求$i$与二元组$(j,k)$一一匹配，那就是二分图匹配啦 具体建模： - 二元组$(j,k)$映射为整数$j\times n+k(j\leq m,k\leq n)$（不会和$i$冲突） - 源点连接$i(i\leq n)$，$(j,k)$连接汇点，容量都为1，费用都为0. - 对于$(i,j\times n+k)$，其容量为1，费用为$t[i][j]\times k$. 然后跑最小费用最大流即可 # 代码 ```cpp #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=1e5,M=1e6,INF=0x3f3f3f3f; int n,m,s,t; struct qxx{int nex,t,v,c;}; qxx e[M]; int h[N],cnt=1; void add_path(int f,int t,int v,int c){e[++cnt]=(qxx){h[f],t,v,c},h[f]=cnt;} void add_flow(int f,int t,int v,int c){add_path(f,t,v,c);add_path(t,f,0,-c);} int dis[N],pre[N],incf[N]; bool vis[N]; bool bfs(){ memset(dis,0x3f,sizeof(dis)); queue<int> q; q.push(s),dis[s]=0,incf[s]=INF,incf[t]=0; while(q.size()){ int u=q.front();q.pop(); vis[u]=0; for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v,&c=e[i].c; if(!w||dis[v]<=dis[u]+c)continue; dis[v]=dis[u]+c,incf[v]=min(w,incf[u]),pre[v]=i; if(!vis[v])q.push(v),vis[v]=1; } } return incf[t]; } int maxflow,mincost; void update(){ maxflow+=incf[t]; for(int u=t;u!=s;u=e[pre[u]^1].t){ e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t]; mincost+=incf[t]*e[pre[u]].c; } } int T[70][20]; int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&T[i][j]); s=0,t=m*n+n+1; for(int i=1;i<=n;i++)add_flow(s,i,1,0); for(int i=n+1;i<=m*n+n;i++)add_flow(i,t,1,0);//二元组 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) add_flow(i,j*n+k,1,T[i][j]*k); while(bfs())update(); printf("%.2lf",mincost*1.0/n); return 0; } ```