点击打开链接
这是挑战上的一道题，不得不说十分的难懂。我看了好久才明白什么意思，当然好像跟挑战上的意思有点区别但是能A就行。
首先，我们知道，这些玩具是可以交给各个工厂去加工的，一个工厂可以加工多个工厂，这里还没什么头绪。
我们来看只有一个工厂的时候，加工n个玩具的总时间就会有T = Z1 + (Z1 + Z2) + .... + (Z1 + Z2 + .... + Zn)
也就是T = n * Z1 + (n - 1) * Z2 + ..... + 1 * Zn
我们可以从上式中看出一些东西，就是玩具i，假设他是在这个工厂里面第k个加工的，那么他就是上面的Zk
我们可以看到，Zk对总时间的贡献就是（n - k + 1） * Zk。
这时候我们就可以把每个工厂给拆点了，拆成了n个点，第k个点代表的是第k个加工。
我们要的是总共的时间最小，那么构图：
一个超级源点连向每个玩具，流量为1，花费为0.
每个工厂拆出来的点连向超级汇点，流量为1，花费为0.
每个玩具i和每个工厂j的第k个加工的点连一条流量为1，花费为(n-k+1)*G[i][j]的边，G[i][j]就是玩具i在j工厂加工的费用。
然后就跑一跑费用流输出即可。
代码如下：
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<utility> #include<stack> #include<algorithm> #include<cstring> #include<string> #include<cmath> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 2600; const int maxm = 260000; int n, m; int head[maxn], to[maxm], front[maxm], flow[maxm], cost[maxm], ppp; int dis[maxn], minflow[maxn]; bool flag[maxn]; pair<int, int> par[maxn]; int G[55][55]; struct MIN_COST_MAX_FLOW{ void init() { memset(head, -1, sizeof(head)); ppp = 0; } bool spfa(int s, int e) { int u, v; for(int i = 0; i <= e; i++) dis[i] = INF; memset(flag, 0, sizeof(flag)); dis[s] = 0; minflow[s] = INF; queue <int> q; q.push(s); while(!q.empty()) { u = q.front(); q.pop(); flag[u] = 0; for(int i = head[u]; ~i; i = front[i]) { v = to[i]; if(flow[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; par[v] = (make_pair(u, i)); minflow[v] = min(minflow[u], flow[i]); if(!flag[v]) { flag[v] = 1; q.push(v); } } } } if(dis[e] == INF) return 0; return 1; } int slove(int s, int e) { int ans = 0, p; while(spfa(s, e)) { p = e; while(p != s) { flow[par[p].second] -= minflow[e]; flow[par[p].second^1] += minflow[e]; p = par[p].first; } ans += dis[e]; } return ans; } void add_edge(int u, int v, int f, int c) { to[ppp] = v, front[ppp] = head[u], flow[ppp] = f, cost[ppp] = c, head[u] = ppp++; to[ppp] = u, front[ppp] = head[v], flow[ppp] = 0, cost[ppp] = -c, head[v] = ppp++; } }mcmf; int main() { // freopen("poj_in.txt", "r", stdin); int T; cin >> T; while(T--) { mcmf.init(); scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &G[i][j]); } } int s = n + m * n + 1, t = s + 1; for(int i = 0; i < n; i++) { mcmf.add_edge(s, i, 1, 0); } for(int j = 0; j < m; j++) { for(int k = 0; k < n; k++) { mcmf.add_edge(n + j * n + k, t, 1, 0); for(int i = 0; i < n; i++) { mcmf.add_edge(i, n + j * n + k, 1, (n - k) * G[i][j]); } } } int ans = mcmf.slove(s, t); printf("%.6f\n", (double)(ans) / n); } return 0; }