构造一个图，左边n∗mn∗m个点，表示第jj个技术人员修的倒数第ii辆车，右边nn个点，表示第kk辆车
源点向左边的点连(w=1,cost=0)(w=1,cost=0)的边，因为每个人同一时刻只能修一辆车
左边m∗nm∗n个点再分别向右边nn个点连边，左边第(i,j)(i,j)个点向右边第kk个点连(w=INF,cost=i∗t[i][j])(w=INF,cost=i∗t[i][j])的边
相当于此时有ii个人在等待着这辆车修完，代价就是等待的人数∗∗修这辆车的时间
右边的点向汇点连(w=1,cost=0)(w=1,cost=0)的边，表示每辆车只能被一个人修
容易看出，此时最大流一定是nn，每一条w=1w=1的流表示第jj个人修的倒数第ii辆车是第kk辆车
那么最小费用除以nn就是我们的答案
我写的代码一直TLE....
本地过了就是过了，OJ上TLE是OJ有问题
#includeusing namespace std;const int MAXN = 10000;const int MAXM = 100000;const int INF = 0x3f3f3f3f;struct Edge{ int to,next,cap,flow,cost;} edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int N;void init(){ tol = 0; memset(head, - 1,sizeof(head));}void addedge(int u,int v,int cap,int cost){ edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = - cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++;}bool spfa(int s,int t){ queue q; memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(pre,-1,sizeof(pre)); dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != - 1; i = edge[i].next){ int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ){ dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; q.push(v); } } } } if(pre[t] == - 1) return false; else return true;}int minCostMaxflow(int s,int t,int &cost){ int flow = 0; cost = 0; while(spfa(s,t)){ int Min = INF; for(int i = pre[t]; i != - 1; i = pre[edge[i^1].to]){ if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t]; i != - 1; i = pre[edge[i^1].to]){ edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return cost;}int n,m;int car[70][70],id_man[70][70],id_car[70];int cnt,s,t;int main(){ cnt = 0; scanf("%d%d",&m,&n); for (int i = 1;i <= n;++i){ for (int j = 1;j <= m;++j){ scanf("%d",&car[i][j]); } } init(); s = cnt++;t = cnt++; for (int i = 1;i <= m;++i){ for (int j = 1;j <= n;++j){ addedge(s,id_man[i][j] = cnt++,1,0); } } for (int i = 1;i <= n;++i){ addedge(id_car[i] = cnt++,t,1,0); } for (int i = 1;i <= m;++i){ //第i个人 for (int j = 1;j <= n;++j){ //倒数第j次 for (int k = 1;k <= n;++k){ //车k addedge(id_man[i][j],id_car[k],1,j*car[k][i]); } } } N = cnt; int cost = 0; printf("%.2f\n",(double)minCostMaxflow(s,t,cost)/n);}
下面是别人的AC代码
#include#include #include #include using namespace std;const int N = 10 + 5;const int M = 60 + 5;const int INF = 0x3f3f3f3f;int n, m;int S, T, cnt;int C[N][M], id1[N][M], id2[M];int head[N * M], len;struct nodeLib { int to, nxt, val, flow; inline void add(int a, int b, int c, int d) { to = b, val = d, flow = c; nxt = head[a], head[a] = len++; }} lib[N * M * M << 1];inline int read() { char ch; int ans = 0, neg = 1; while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') neg = -1; while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar(); return ans * neg;}inline void makePath(int a, int b, int c, int d) { lib[len].add(a, b, c, d); lib[len].add(b, a, 0, -d);}void init() { n = read(), m = read(); len = 2, S = ++cnt, T = ++cnt; for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++) C[i][j] = read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) makePath(S, id1[i][j] = ++cnt, 1, 0); for (int i = 1; i <= m; i++) makePath(id2[i] = ++cnt, T, 1, 0); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= m; k++) makePath(id1[i][j], id2[k], 1, j * C[i][k]);}queue Q;bool inQ[N * M];int dist[N * M], preE[N * M], preV[N * M];bool SPFA() { memset(dist, 0x3f, sizeof(dist)); dist[S] = 0, Q.push(S), inQ[S] = true; while (!Q.empty()) { int tmp = Q.front(); Q.pop(), inQ[tmp] = false; for (int p = head[tmp]; p; p = lib[p].nxt) { int now = lib[p].to, val = lib[p].val; if (lib[p].flow && dist[now] > dist[tmp] + val) { dist[now] = dist[tmp] + val; preE[now] = p, preV[now] = tmp; if (!inQ[now]) Q.push(now), inQ[now] = true; } } } return dist[T] != INF;}int MCMF() { int ans = 0; while (SPFA()) { int maxf = INF; for (int p = T; p != S; p = preV[p]) maxf = min(maxf, lib[preE[p]].flow); for (int p = T; p != S; p = preV[p]) lib[preE[p]].flow -= maxf, lib[preE[p] ^ 1].flow += maxf; ans += dist[T] * maxf; } return ans;}int main() { init(); printf("%.2lf\n", (double)MCMF() / m); return 0;}