洛谷 P2053 [SCOI2007] 修车

题目相关

题目链接: 洛谷 P2053 [SCOI2007] 修车

题目描述

同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 $M$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。

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

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

输入格式

第一行有两个数 $M,N$，表示技术人员数与顾客数。

接下来 $N$ 行，每行 $M$ 个整数。第 $i+1$ 行第 $j$ 个数表示第 $j$ 位技术人员维修第 $i$ 辆车需要用的时间 $T_{i,j}$。

输出格式

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

样例 #1

样例输入 #1

2 2
3 2
1 4

样例输出 #1

1.50

提示

对于 $100%$ 的数据，$2\le M\le 9$，$1\le N\le 60$，$1\le T\le 10^3$。

题目解析

首先这道题要知道：

1. 一个人在某一时刻只能修一辆车/在偷懒

2. 一辆车在某一时刻只能被一个人修/被抛弃

如果要从让工人老老实实从第一辆车修到最后一辆车这样的思路去想，

那么可以去想一个非常巧妙的贪心，然而数据范围否定了我的想法。

正着建图有点艰难，我们换一种思路。

前面修的车会对后面修的车产生影响，影响难以确定，但是后面的车对前面的没有什么影响。

我们就可以反过来思考，设第 $i$ 个工人修第 $j$ 辆车要的时间为 $t_m$，

那么如果这辆车是倒数第 $k$ 个被修的，他的贡献就是 $k\cdot t_m$，

因为后面 $k-1$ 辆车要等这一段时间，当然还要加上这辆车本身。

所以思路出来了，建图如下：

1. 把工人拆成n个点，代表每个工人修的倒数第几辆车

2. S->顾客（也就是每辆车），flow=1，cost=0

3. 顾客（每辆车）->修车情况（也就是①）：

　第 $i$ 个顾客（车），第 $j$ 个工人修的倒数第k辆车：

　flow=1，cost=k*(tm[j][i]*k)，其中tm[j][i]代表第j个工人修第i辆车话费的时间。

4. 修车情况->T，flow=1，cost=0

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int maxn=10010;
struct line{
	int u,v;
	int cap,flow,cost;
};
vector<line> edge;
vector<int> G[maxn];
int dis[maxn],a[maxn],pre[maxn];
bool vis[maxn];
int n,m,S,T;
int t[10][70];
double ans;
void addedge(int from,int to,int cap,int cost){
	edge.push_back((line){from,to,cap,0,cost});
	edge.push_back((line){to,from,0,0,-cost});
	int m=edge.size();
	G[from].push_back(m-2);
	G[to].push_back(m-1);
}
bool spfa(int &minc){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	queue<int> q; q.push(S);
	vis[S]=true; dis[S]=0;
	a[S]=2147483647;
	while(!q.empty()){
		int u=q.front(); q.pop();
		vis[u]=false;
		for (int i=0;i<G[u].size();++i){
			line e=edge[G[u][i]];
			if (e.cap>e.flow&&dis[e.v]>dis[u]+e.cost){
				pre[e.v]=G[u][i];
				dis[e.v]=dis[u]+e.cost;
				a[e.v]=min(a[u],e.cap-e.flow);
				if (!vis[e.v]){
					vis[e.v]=true;
					q.push(e.v);
				} 
			}
		}
	}
	if (dis[T]==dis[maxn-1]) return false;
	minc+=a[T]*dis[T];
	int u=T;
	while (u!=S){
		edge[pre[u]].flow+=a[T];
		edge[pre[u]^1].flow-=a[T];
		u=edge[pre[u]].u;
	}
	return true;
}
int mcmf(){
	int mincost=0;
	while (spfa(mincost));
	return mincost;
}
int main(){
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			scanf("%d",&t[j][i]);
		}
	}
	S=0; T=n*m+n+1;
	for (int i=1;i<=n;++i){
		addedge(S,n*m+i,1,0);
	}
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			for (int k=1;k<=n;++k){
				addedge(n*m+i,(j-1)*n+k,1,t[j][i]*k);
			}
		}
	}
	for (int j=1;j<=m;++j){
		for (int k=1;k<=n;++k){
			addedge((j-1)*n+k,T,1,0);
		}
	}
	ans=mcmf(); ans=(double)ans/(double)n;
	printf("%.2lf",ans);
	return 0;
}