假设用一个厂来处理所有物品，很容易推出总时间T=n*t1+（n-1）*t2+...+1*tn,根据这个式子我们可以把一个处理n个物品的厂看做n个处理一个物品的厂，处理时间分别乘n、n-1...1，这样的话最终有n个物品和n*m个厂，且这n*m个厂都是只能处理一个物品，典型的指派问题，增加源点汇点建图后跑一遍最小费用流即可，顺便再次注意一下c++和g++的区别——g++用.f，c++用.lf
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 3000; const int INF = 0x3f3f3f3f; //========================= typedef pair<int, int> P; struct Edge { int to, cap, cost, rev; Edge(int a, int b, int c, int d) : to(a), cap(b), cost(c), rev(d) {} }; int V; vector<Edge> G[maxn]; int h[maxn]; int dist[maxn]; int prevv[maxn], preve[maxn]; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int u, int v, int cap, int cost) { G[u].push_back(Edge(v, cap, cost, G[v].size())); G[v].push_back(Edge(u, 0, -cost, G[u].size()-1)); } int min_cost_flow(int s, int t, int f) { int res = 0; memset(h, 0, sizeof(h)); while (f > 0) { priority_queue<P, vector<P>, greater<P> > q; memset(dist, INF, sizeof(dist)); dist[s] = 0; q.push(P(0, s)); while (!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; q.push(P(dist[e.to], e.to)); } } } if (dist[t] == INF) return -1; for (int v = 0; v < V; v++) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d*h[t]; for (int v = t; v != s; v = prevv[v]) { Edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } //========================== int T, n, m, z[maxn][maxn]; void solve() { int s = n+n*m; int t = s + 1; V = t+1; for (int i = 0; i < n; i++) addedge(s, i, 1, 0); for (int j = 0; j < m; j++) { for (int k = 0; k < n; k++) { addedge(n+j*n+k, t, 1, 0); for (int i = 0; i < n; i++) { addedge(i, n+j*n+k, 1, (k+1)*z[i][j]); } } } printf("%.6lf\n", 1.0*min_cost_flow(s, t, n) / n); } int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); init(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) scanf("%d", &z[i][j]); } solve(); } return 0; }