刚做费用流，思路完全不对呀……
应该这么想（应该说敢这么想）：这道题的关键在于怎么体现这个玩具是第几个加工的，只有这才能求出他的加工时间（因为加工时间包括等待时间）。
但等待时间不好求，因此要换个思路想：加工这个玩具会对别的玩具的加工时间造成多少影响。
假设三个玩具
\(i, j, k\)依次在同一个工厂中被加工出来，那么总时间
\(T = t_i + (t_i + t_j) + (t_i + t_j + t_k) = 3 * t_i + 2 * t_j + t_k\)。所以一个玩具对总时间的贡献是：加工次序
\(*\)制作时间。
那么建图就有思路了：把每一个工厂拆成
\(n\)个点，代表加工次序。对于每一个玩具
\(i\)，向每一个工厂
\(j\)的每一个加工次序的点
\(k\)连一条容量为1，费用为
\(k * cost_{i, j}\)的边。然后从源点向玩具连边，从每一个拆开的的工厂向汇点连边。
跑费用流。
最后要提醒的是算好空间。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define rg registertypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int N = 50;const int maxn = N + N * N + 5;const int maxe = N + N * N + N * N * N + 5;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, m, s, t, a[N + 5][N + 5];struct Edge{ int nxt, from, to, cap, c;}e[maxe << 1];int head[maxn], ecnt = -1;void addEdge(int x, int y, int w, int c){ e[++ecnt] = (Edge){head[x], x, y, w, c}; head[x] = ecnt; e[++ecnt] = (Edge){head[y], y, x, 0, -c}; head[y] = ecnt;}bool in[maxn];int dis[maxn], pre[maxn], flow[maxn];bool spfa(){ Mem(in, 0); Mem(dis, 0x3f); in[s] = 1; dis[s] = 0; flow[s] = INF; queue q; q.push(s); while(!q.empty()) { int now = q.front(); q.pop(); in[now] = 0; for(int i = head[now], v; i != -1; i = e[i].nxt) { v = e[i].to; if(e[i].cap > 0 && dis[now] + e[i].c < dis[v]) { dis[v] = dis[now] + e[i].c; pre[v] = i; flow[v] = min(flow[now], e[i].cap); if(!in[v]) in[v] = 1, q.push(v); } } } return dis[t] != INF;}int minCost = 0;void update(){ int x = t; while(x != s) { int i = pre[x]; e[i].cap -= flow[t]; e[i ^ 1].cap += flow[t]; x = e[i].from; } minCost += flow[t] * dis[t];}void MCMF(){ while(spfa()) update();}int main(){ int T = read(); while(T--) { Mem(head, -1); ecnt = -1; minCost = 0; n = read(); m = read(); s = 0, t = n + n * m + 1; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) a[i][j] = read(); for(int i = 1; i <= n; ++i) { addEdge(s, i, 1, 0); for(int j = 1; j <= m; ++j) for(int k = 1; k <= n; ++k) addEdge(i, j * n + k, 1, k * a[i][j]); } for(int i = n + 1; i <= n * m + n; ++i) addEdge(i, t, 1, 0); MCMF(); printf("%.6f\n", (db)minCost / (db)n); } return 0;}