本文共 2561 字，大约阅读时间需要 8 分钟。
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
最小平均等待时间，答案精确到小数点后2位。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define pb(x) push_back(x)#define ll long long#define mk(x, y) make_pair(x, y)#define lson l, m, rt<<1#define mem(a) memset(a, 0, sizeof(a))#define rson m+1, r, rt<<1|1#define mem1(a) memset(a, -1, sizeof(a))#define mem2(a) memset(a, 0x3f, sizeof(a))#define rep(i, n, a) for(int i = a; i pll;const double PI = acos(-1.0);const double eps = 1e-8;const int mod = 1e9+7;const int inf = 1061109567;const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };const int maxn = 2e5+5;int num, head[maxn*2], s, t, n, k, nn, dis[maxn], flow, cost, cnt, cap[maxn], q[maxn], cur[maxn], vis[maxn];struct node{ int to, nextt, c, w; node(){} node(int to, int nextt, int c, int w):to(to), nextt(nextt), c(c), w(w) {}}e[maxn*2];int spfa() { int st, ed; st = ed = 0; mem2(dis); ++cnt; dis[s] = 0; cap[s] = inf; cur[s] = -1; q[ed++] = s; while(st dis[u]+w) { dis[v] = dis[u]+w; cap[v] = min(c, cap[u]); cur[v] = i; if(vis[v] != cnt) { vis[v] = cnt; q[ed++] = v; } } } } if(dis[t] == inf) return 0; cost += dis[t]*cap[t]; flow += cap[t]; for(int i = cur[t]; ~i; i = cur[e[i^1].to]) { e[i].c -= cap[t]; e[i^1].c += cap[t]; } return 1;}int mcmf() { flow = cost = 0; while(spfa()) ; return cost;}void add(int u, int v, int c, int val) { e[num] = node(v, head[u], c, val); head[u] = num++; e[num] = node(u, head[v], 0, -val); head[v] = num++;}void init() { mem1(head); num = cnt = 0; mem(vis);}int a[65][10];int main(){ int n, m; cin>>m>>n; init(); for(int i = 1; i<=n; i++) { for(int j = 1; j<=m; j++) { scanf("%d", &a[i][j]); } } s = n*m+n+1, t = s+1; for(int i = 1; i<=n*m; i++) { add(s, i, 1, 0); } for(int i = n*m+1; i<=n*m+n; i++) { add(i, t, 1, 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, n*m+k, 1, j*a[k][i]); } } } printf("%.2f\n", 1.0*mcmf()/n); return 0;}
转载于:https://www.cnblogs.com/yohaha/p/5228642.html