本文共 2331 字，大约阅读时间需要 7 分钟。

题意：自行脑补，看懂分段函数是什么就行。

思路：显然是最小费用最大流。

对于每个工作人员的每一段，从原点到工作人员对应的点连一条费用与流量与这一段其相适应的边。

对于每个部件，从其对应的点到汇点连一条流量为需要的数目，费用为0的边。

然后就可以出解了。

建模还是很显然的。

还有这题我写spfa的多路增广TLE了，反倒是不加上多路增广能过。不知道为什么。。。

Code:

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define N 260#define M 260#define INF 0x3f3f3f3fqueue
         
           q;struct Solver { int head[M*7+N],next[N*M*6],end[N*M*6],flow[N*M*6],cost[N*M*6],ind; int dis[M*7+N], ld[M*7+N], lb[M*7+N]; bool inq[M*7+N]; void reset() { ind = 0; memset(head, -1, sizeof(head)); } void addedge(int a, int b, int _flow, int _cost) { //printf("%d %d flow=%d cost=%d\n", a, b, _flow, _cost); int q = ind++; flow[q] = _flow; cost[q] = _cost; end[q] = b; next[q] = head[a]; head[a] = q; } void make(int a, int b, int _flow, int _cost) { addedge(a, b, _flow, _cost); addedge(b, a, 0, -_cost); } bool spfa(int S, int T) { inq[S] = 1; q.push(S); memset(dis, 0x3f, sizeof dis); dis[S] = 0; int i, j; while(!q.empty()) { i = q.front(); q.pop(); inq[i] = 0; for(j = head[i]; j != -1; j = next[j]) { if (flow[j] && dis[end[j]] > dis[i] + cost[j]) { ld[end[j]] = i; lb[end[j]] = j; dis[end[j]] = dis[i] + cost[j]; if (!inq[end[j]]) { inq[end[j]] = 1; q.push(end[j]); } } } } return dis[T] != 0x3f3f3f3f; } long long Mincost(int S, int T) { long long res = 0; int Min, i; while(spfa(S, T)) { Min = INF; for(i = T; i != S; i = ld[i]) Min = Min > flow[lb[i]] ? flow[lb[i]] : Min; res += (long long)Min * dis[T]; for(i = T; i != S; i = ld[i]) flow[lb[i]] -= Min, flow[lb[i] ^ 1] += Min; } return res; }}G;int s[M][N];int num[N], size[M], ins[M][7], w[M][7], id;int main() { int m, n; scanf("%d%d", &m, &n); register int i, j, k; for(i = 1; i <= n; ++i) scanf("%d", &num[i]); for(i = 1; i <= m; ++i) for(j = 1; j <= n; ++j) scanf("%d", &s[i][j]); id = n; for(i = 1; i <= m; ++i) { scanf("%d", &size[i]); for(j = 1; j <= size[i]; ++j) scanf("%d", &ins[i][j]); for(j = 1; j <= size[i] + 1; ++j) scanf("%d", &w[i][j]); } G.reset(); for(i = 1; i <= n; ++i) G.make(i, n + m + 1, num[i], 0); for(i = 1; i <= m; ++i) { for(j = 1; j <= size[i]; ++j) G.make(0, n + i, ins[i][j] - ins[i][j - 1], w[i][j]); G.make(0, n + i, INF, w[i][size[i] + 1]); for(j = 1; j <= n; ++j) if (s[i][j]) G.make(n + i, j, INF, 0); } printf("%lld", G.Mincost(0, n + m + 1)); return 0;}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/wyfcyx_forever/article/details/40346625 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！