网络流——最小费用流。

好久没写了板子都快忘了。将m个工人拆成n个点，点（i，j）表示让i工人在倒数第j辆车时去修连向这个点的车，那么显而易见代价为j*ti（后面的人要等）。

1 #include
     
       2 using namespace std; 3 #define N 70 4 #define M 15 5 #define INF 1e9 6 int n,m,cnt=2,ti[M][N],head[5005],p[5005],a[5005],ans,d[5005],S,T; 7 bool vis[5005]; 8 queue
      
       q; 9 struct edges{10     int fr,to,cap,flow,cost,next;11 }e[100005];12 void inser(int u,int v,int c,int co){13     e[cnt]=(edges){u,v,c,0,co,head[u]};head[u]=cnt++;14     e[cnt]=(edges){v,u,0,0,-co,head[v]};head[v]=cnt++;15 }16 bool spfa(){17     memset(d,0x3f,sizeof(d));18     q.push(S); d[S]=0; a[S]=INF;19     while(!q.empty()){20         int x=q.front(); q.pop(); vis[x]=0;21         for(int i=head[x];i;i=e[i].next){22             if(d[e[i].to]>d[x]+e[i].cost && e[i].cap>e[i].flow){23                 d[e[i].to]=d[x]+e[i].cost; p[e[i].to]=i; a[e[i].to]=min(a[x],e[i].cap-e[i].flow);24                 if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);25             }26         }27     }28     return d[T]