考虑把车间拆点,对付每个时间的车间拆开,这样对付第i个订单来说,他在第j个车间被倒数第k个措置惩罚惩罚就要花费k*z[i][j]的时间
建图:
1.S向每个任务连w=1,c=0边
2.每个任务向每个被拆开的车间连 w=1,c=k*z[i][j]的边
3.每个被拆开的车间向汇点连w=1,c=0边
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define N 1010 #define INF 1000000000 using namespace std; int ecnt=1,vis[N*N],dist[N*N],n,m,S,T,ans,head[N*N],test,z[N][N],tot; deque <int> q; struct adj { int nxt,v,w,c; }e[1000010]; inline void add(int u,int v,int w,int c) { e[++ecnt].v=v,e[ecnt].w=w,e[ecnt].c=c,e[ecnt].nxt=head[u],head[u]=ecnt; e[++ecnt].v=u,e[ecnt].w=0,e[ecnt].c=-c,e[ecnt].nxt=head[v],head[v]=ecnt; } inline int spfa(int s,int t) { int v; memset(vis,0,sizeof(vis)); for (int i=S;i<=T;i++) dist[i]=INF; dist[t]=0,vis[t]=1; q.push_back(t); while (!q.empty()) { int u=q.front();q.pop_front(); for (int i=head[u];i;i=e[i].nxt) if (e[i^1].w>0 && dist[v=e[i].v]>dist[u]-e[i].c) { dist[v]=dist[u]-e[i].c; if (!vis[v]) { vis[v]=1; if (!q.empty() && dist[v]<dist[q.front()]) q.push_front(v); else q.push_back(v); } } vis[u]=0; } return dist[s]<INF; } inline int dfs(int x,int flow) { if (x==T) return vis[T]=1,flow; int used=0,tmp,v; vis[x]=1; for (int i=head[x];i;i=e[i].nxt) if (!vis[v=e[i].v] && e[i].w>0 && dist[x]-e[i].c==dist[v]) { tmp=dfs(v,min(e[i].w,flow-used)); if (tmp>0) ans+=tmp*e[i].c,e[i].w-=tmp,e[i^1].w+=tmp,used+=tmp; if (used==flow) break; } return used; } inline int CostFlow() { int Flow=0; while (spfa(S,T)) { vis[T]=1; while (vis[T]) { memset(vis,0,sizeof(vis)); Flow+=dfs(S,INF); } } return Flow; } void init() { memset(head,0,sizeof(head)); ecnt=1; S=0,T=n*m+n+1; ans=0; } int main() { scanf("%d",&test); while (test--) { scanf("%d%d",&n,&m); init(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&z[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) add(i,j*n+k,1,z[i][j]*k); for (int i=1;i<=n;i++) add(S,i,1,0); for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) add(i*n+j,T,1,0); CostFlow(); printf("%.6f\n",1.0*ans/n); } return 0; }
，