https://www.luogu.org/problem/P2053
题目描述
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
输入格式
第一行有两个数M,N，表示技术人员数与顾客数。
接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
输出格式
最小平均等待时间，答案精确到小数点后2位。
输入输出样例
输入 #1
2 2
3 2
1 4输出 #1
1.50说明/提示
(2<=M<=9,1<=N<=60), (1<=T<=1000)
解题思路：
把每个工作人员拆分为n个，代表每个阶段的工人，这样一共有n*m个，源点和车费0流1， 每个阶段的工人和汇点费0流1，每个车与第i个阶段的工人的费用为 i*cost，代表如果这个工人后面有i-1个需要修理的车，需要等待的时间，求出最小费用流。
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 1020
using namespace std;
struct edge{
int v;
int w;
int cost;
int rev;
};
vector<edge>e[N];
int n, m, prevv[N], preve[N], dis[N], inf=0x3f3f3f3f;
int add(int u, int v, int w, int cost)
{
e[u].push_back(edge{v, w, cost, e[v].size()});
e[v].push_back(edge{u, 0, -cost, e[u].size()-1});
}
int min_cost(int s, int t)
{
int ans=0;
while(1)
{
for(int i=0; i<=t; i++)
dis[i]=inf;
dis[s]=0;
bool update=true;
while(update)
{
update=false;
for(int v=0; v<=t; v++)
{
if(dis[v]==inf)
continue;
for(int i=0; i<e[v].size(); i++)
{
edge &G=e[v][i];
if(G.w && dis[G.v]>dis[v]+G.cost)
{
dis[G.v]=dis[v]+G.cost;
prevv[G.v]=v;
preve[G.v]=i;
update=true;
}
}
}
}
if(dis[t]==inf)
return ans;
int d=1;
// for(int v=t; v!=s; v=prevv[v])
// {
// d=min(d, e[prevv[v]][preve[v]].w);
// }
ans+=d*dis[t];
for(int v=t; v!=s; v=prevv[v])
{
edge &G = e[prevv[v]][preve[v]];
G.w-=d;
e[v][G.rev].w+=d;
}
}
return ans;
}
int main()
{
int w;
while(scanf("%d%d", &m, &n)!=EOF)
{
int s=0, t=n*(m+1)+1;
for(int i=1; i<=t; i++)
e[i].clear();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
scanf("%d", &w);
for(int k=1; k<=n; k++)
add(i, j*n+k, 1, w * k);
}
for(int i=1; i<=n; i++)
add(s, i, 1, 0);
for(int i=n+1; i<t; i++)
add(i, t, 1, 0);
printf("%.2lf
", 1.0*min_cost(s, t)/n);
}
return 0;
}