题意：有m个工厂，n个订单，问平均完成时间
思路：假设一个工厂依次完成n1,n2,n3，时间为3*t1 + 2*t2 + t3，一个任务在倒数第k个完成，时间为k*t。
把一个工厂分为n个时间点，枚举每个任务完成的时间，连到相应的时间点，每个工厂的时间点汇集在起点，容量为1，每个任务汇集在终点，容量为1，费用都为0
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; const int maxn = 2600; struct edge { int to,cf,w,rev; }; int d[maxn],fa[maxn],inq[maxn],pr[maxn]; vector<struct edge> v[maxn]; void init(int x) { for(int i = 0; i <= x; i++) v[i].clear(); } void add(int from,int to,int cap,int cost) { v[from].push_back((edge){to,cap,cost,v[to].size()}); v[to].push_back((edge){from,0,-cost,v[from].size()-1}); } int mincost(int s,int t) { queue<int> q; while(!q.empty()) q.pop(); int c,f; c = f = 0; while(1) { memset(fa,-1,sizeof fa); memset(d,0x3f,sizeof d); d[s] = 0; memset(inq,0,sizeof inq); q.push(s); while(!q.empty()) { int x = q.front();q.pop(); inq[x] = 0; for(int i = 0; i < v[x].size(); i++) { edge e = v[x][i]; int y = e.to; if(e.cf && d[y] > d[x] + e.w) { d[y] = d[x] + e.w; fa[y] = x; pr[y] = i; if(!inq[y]) { inq[y] = 1; q.push(y); } } } } if(d[t] == 0x3f3f3f3f) break; int gen = 0x3f3f3f3f; for(int a = t; a != s; a = fa[a]) gen = min(gen,v[fa[a]][pr[a]].cf); for(int a = t; a != s; a = fa[a]) { edge &e = v[fa[a]][pr[a]]; e.cf -= gen; v[a][e.rev].cf += gen; } f += gen; c += gen * d[t]; } return c;//f 最大流，c最小费用 } int main(void) { int T,n,m,i,j,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); int s = 1; int t = 2 + m*n + n; init(t); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { int tp; scanf("%d",&tp); for(k = 1; k <= n; k++) { add(1+(j-1)*n+k,1+n*m+i,1,k * tp); } } } for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { add(1,1+(i-1)*n+j,1,0); } } for(i = 1; i <= n; i++) add(1+n*m+i,t,1,0); double ans = mincost(s,t) / (n*1.0); printf("%f\n",ans); } return 0; }
G++编译，double 输出要用%f
