Rockdu's Blog

【题目描述】

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

【输入】

第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

【输出】

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

【输入样例】

2 2
3 2
1 4

【输出样例】

1.50

【提示】

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

【来源】

没有写明来源

神奇的网络流题目。考虑：让第i辆车成为第j个修理工修理的第k辆，对答案的贡献。但是因为我们不知道这个修理工之后还有多少车要修，我们没有办法统计贡献。这是，我们不妨用逆向思维：我们让第i辆车成为第j个修理工修理的倒数第k辆，这样我们就知道这辆车被修后对答案的贡献了。于是我们把修理工拆成车辆那么多个点，表示倒数第k辆修的车就行了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
	int v, w, cost, next;
}e[maxn << 2];
int head[maxn], cnt, n, m, ndcnt, S, T;
void adde(const int &u, const int &v, const int &w, const int &cost) {
	e[cnt] = (edge) {v, w, cost, head[u]};
	head[u] = cnt++;
	e[cnt] = (edge) {u, 0, -cost, head[v]};
	head[v] = cnt++;
}
int worker[105][105], car[105], tm[105][105];

queue<int > q;
int vis[maxn], dis[maxn], fa[maxn], id[maxn];
int SPFA(int s, int t) {
	memset(dis, 0x3f, sizeof(int) * (ndcnt + 5));
	dis[s] = 0, q.push(s);
	while(!q.empty()) {
		int u = q.front(), v;q.pop(), vis[u] = 0;
		for(register int i = head[u]; ~i; i = e[i].next) {
			v = e[i].v;
			if(!e[i].w) continue;
			if(dis[v] > dis[u] + e[i].cost) {
				id[v] = i, fa[v] = u;
				dis[v] = dis[u] + e[i].cost;
				if(vis[v]) continue;
				vis[v] = 1, q.push(v);
			}
		}
	}
	return dis[t] == inf ? -1 : dis[t];
}

int fdmn(int s, int u) {
	if(u == s) return inf;
	return min(e[id[u]].w, fdmn(s, fa[u]));
}

void ext(int s, int u, int w) {
	if(u == s) return ;
	e[id[u]].w -= w, e[id[u] ^ 1].w += w;
	ext(s, fa[u], w);
}

int Minflow(int s, int t) {
	int ans = 0, now = 0, mn;
	while(1) {
		now = SPFA(s, t);
		if(now == -1) break;
		ans += now * (mn = fdmn(s, t));
		ext(s, t, mn);
	}
	return ans;
}

int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &m, &n), S = ++ndcnt, T = ++ndcnt;
	for(register int i = 1; i <= n; ++i)
		for(register int j = 1; j <= m; ++j)
			scanf("%d", &tm[i][j]);
	for(register int i = 1; i <= n; ++i)
		for(register int j = 1; j <= m; ++j)
			worker[j][i] = ++ndcnt, adde(ndcnt, T, 1, 0);
	for(register int i = 1; i <= n; ++i) {
		car[i] = ++ndcnt, adde(S, ndcnt, 1, 0);
		for(register int j = 1; j <= n; ++j) {
			for(register int k = 1; k <= m; ++k)
				adde(car[i], worker[k][j], 1, tm[i][k] * j);
		}
	}
	printf("%.2lf", (double)Minflow(S, T) / n);
	return 0;
}