http://poj.org/problem?id=3686
拆点很巧妙 将每个M个点拆成m*n个点 分别表示第i个玩具在第j个机器上倒数第K个处理
假设这k个玩具真正用在加工的时间分为a1,a2,a3...ak, 那么每个玩具实际的时间是加工的时间+等待时间，分别为
a1, a1+a2, a1+a2+a3.......a1+a2+...ak
求和之后变为 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<stdlib.h> 7 #define INF 0xfffffff 8 #define N 55 9 #define M 2555 10 using namespace std; 11 int w[N][M],n,m,p,lx[N],d,ly[M],link[M],x[N],y[M]; 12 bool match(int u) 13 { 14 x[u] = 1; 15 for(int i = 1; i <= p ; i++) 16 { 17 if(y[i]) continue; 18 int o = lx[u]+ly[i]-w[u][i]; 19 if(o==0) 20 { 21 y[i] = 1; 22 if(!link[i]||match(link[i])) 23 { 24 link[i] = u; 25 return true; 26 } 27 } 28 else if(o<d) d = o; 29 } 30 return false; 31 } 32 void km() 33 { 34 int i,j; 35 for(i = 1 ;i <= n ;i++) 36 lx[i] = -INF; 37 memset(ly,0,sizeof(ly)); 38 memset(link,0,sizeof(link)); 39 for(i = 1; i <= n ;i++) 40 for(j = 1; j <= p ;j++) 41 lx[i] = max(lx[i],w[i][j]); 42 for(i = 1; i <= n ;i++) 43 { 44 for(;;) 45 { 46 d = INF; 47 memset(x,0,sizeof(x)); 48 memset(y,0,sizeof(y)); 49 if(match(i)) break; 50 for(j =1 ;j <= n ;j++) if(x[j]){lx[j]-=d;} 51 for(j =1 ;j <= p ;j++) if(y[j]){ly[j]+=d;} 52 } 53 } 54 } 55 int main() 56 { 57 int cas,i,j,k,a; 58 cin>>cas; 59 while(cas--) 60 { 61 scanf("%d%d",&n,&m); 62 for(i = 1 ;i <= n ;i++) 63 for(j = 1 ;j <= m ; j++) 64 { 65 scanf("%d",&a); 66 for(k = 1 ; k <= n ;k++) 67 w[i][(j-1)*n+k] = -1*k*a; 68 } 69 p = n*m; 70 double s=0; 71 km(); 72 73 for(i = 1 ;i <= p ; i++) 74 if(link[i]) 75 { 76 s-=w[link[i]][i]; 77 } 78 printf("%.6f ",1.0*s/n); 79 } 80 return 0; 81 }