題目描述

你的公司接到了一批訂單。訂單要求你的公司提供n類產品，產品被編號為1~n，其中第i類產品共需要C_i件。公司共有m名員工，員工被編號為1~m員工能夠制造的產品種類有所區別。一件產品必須完整地由一名員工制造，不可以由某名員工制造一部分配件后，再轉交給另外一名員工繼續進行制造。

我們用一個由0和1組成的m*n的矩陣A來描述每名員工能夠制造哪些產品。矩陣的行和列分別被編號為1~m和1~n，A_i,j為1表示員工i能夠制造產品j，為0表示員工i不能制造產品j。

如果公司分配了過多工作給一名員工，這名員工會變得不高興。我們用憤怒值來描述某名員工的心情狀態。憤怒值越高，表示這名員工心情越不爽，憤怒值越低，表示這名員工心情越愉快。員工的憤怒值與他被安排制造的產品數量存在某函數關系，鑒于員工們的承受能力不同，不同員工之間的函數關系也是有所區別的。

對于員工i，他的憤怒值與產品數量之間的函數是一個S_i+1段的分段函數。當他制造第1~T_i,1件產品時，每件產品會使他的憤怒值增加W_i,1，當他制造第T_i,1+1~T_i,2件產品時，每件產品會使他的憤怒值增加W_i,2……為描述方便，設T_i,0=0,T_i,si+1=+∞，那么當他制造第T_i,j-1+1~T_i,j件產品時，每件產品會使他的憤怒值增加W_i,j，?1≤j≤S_i+1。

你的任務是制定出一個產品的分配方案，使得訂單條件被滿足，并且所有員工的憤怒值之和最小。由于我們并不想使用Special Judge，也為了使選手有更多的時間研究其他兩道題目，你只需要輸出最小的憤怒值之和就可以了。

輸入

第一行包含兩個正整數m和n，分別表示員工數量和產品的種類數；

第二行包含n?個正整數，第i個正整數為C_i；

以下m行每行n?個整數描述矩陣A；

下面m個部分，第i部分描述員工i的憤怒值與產品數量的函數關系。每一部分由三行組成：第一行為一個非負整數S_i，第二行包含S_i個正整數，其中第j個正整數為T_i,j，如果S_i=0那么輸入將不會留空行（即這一部分只由兩行組成）。第三行包含S_i+1個正整數，其中第j個正整數為W_i,j。W_i,j<W_i,j+1

輸出

僅輸出一個整數，表示最小的憤怒值之和。

樣例輸入

2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6

樣例輸出

24

---

題解

費用流

由于題目中限定了W(i,j)<W(i,j+1)，因此可以直接拆邊費用流。

那么建圖很顯然：S->每種產品，容量為Ci，費用為0；每種產品->能夠生產它的人，容量為inf，費用為0；每個人->T連Si+1條邊，第i條邊容量為Ti - Ti-1，費用為Wi。

然后跑最小費用最大流即可。注意需要開long long

一個小優化：邊上的費用只出現在與S/T之一相連的邊中，這種情況下把帶邊權的邊放到T一端能夠大大減小時間復雜度，這也使得本題直接使用EK費用流即可AC。

#include <queue> #include <cstdio> #include <cstring> #define N 510 #define M 1000010 using namespace std; const int inf = 1 << 30; queue<int> q; int temp[10] , head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N]; void add(int x , int y , int v , int c) {to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt; } bool spfa() {int x , i;memset(from , -1 , sizeof(from));memset(dis , 0x3f , sizeof(dis));dis[s] = 0 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i])if(val[i] && dis[to[i]] > dis[x] + cost[i])dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);}return ~from[t]; } long long mincost() {long long ans = 0;int i , k;while(spfa()){k = inf;for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);ans += k * dis[t];for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;}return ans; } int main() {int m , n , i , j , k , x;scanf("%d%d" , &m , &n) , s = 0 , t = n + m + 1;for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , add(s , i , x , 0);for(i = 1 ; i <= m ; i ++ ){for(j = 1 ; j <= n ; j ++ ){scanf("%d" , &x);if(x) add(j , i + n , inf , 0);}}for(i = 1 ; i <= m ; i ++ ){scanf("%d" , &k);for(j = 1 ; j <= k ; j ++ ) scanf("%d" , &temp[j]);temp[k + 1] = inf;for(j = 1 ; j <= k + 1 ; j ++ ) scanf("%d" , &x) , add(i + n , t , temp[j] - temp[j - 1] , x);}printf("%lld\n" , mincost());return 0; }

?

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7411542.html

總結

以上是生活随笔為你收集整理的【bzoj2245】[SDOI2011]工作安排 费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。