Candy Factory
Time Limit: 2000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 478064-bit integer IO format: %I64d Java class name: Main
A new candy factory opens in pku-town. The factory import M machines to produce high quality candies. These machines are numbered from 1 to M.
There are N candies need to be produced. These candies are also numbered from 1 to N. For each candy i , it can be produced in any machine j. It also has a producing time(si,ti) , meaning that candy i must start producing at time si and will finish at ti. Otherwise if the start time is pi(si < pi< ti) then candy will still finish at ti but need additional K*(pi - si) cost. The candy can’t be produced if pi is greater than or equal to ti. Of course one machine can only produce at most one candy at a time and can’t stop once start producing.
On the other hand, at time 0 all the machines are in their initial state and need to be “set up” or changed before starting producing. To set up Machine j from its initial state to the state which is suitable for producing candiy i, the time required is Cij and cost is Dij. To change a machine from the state suitable for candy i1 into the state suitable for candy i2, time required is Ei1i2 and cost is Fi1i2.
As the manager of the factory you have to make a plan to produce all the N candies. While the sum of producing cost should be minimized.
There are N candies need to be produced. These candies are also numbered from 1 to N. For each candy i , it can be produced in any machine j. It also has a producing time(si,ti) , meaning that candy i must start producing at time si and will finish at ti. Otherwise if the start time is pi(si < pi< ti) then candy will still finish at ti but need additional K*(pi - si) cost. The candy can’t be produced if pi is greater than or equal to ti. Of course one machine can only produce at most one candy at a time and can’t stop once start producing.
On the other hand, at time 0 all the machines are in their initial state and need to be “set up” or changed before starting producing. To set up Machine j from its initial state to the state which is suitable for producing candiy i, the time required is Cij and cost is Dij. To change a machine from the state suitable for candy i1 into the state suitable for candy i2, time required is Ei1i2 and cost is Fi1i2.
As the manager of the factory you have to make a plan to produce all the N candies. While the sum of producing cost should be minimized.
Input
There are multiple test cases.
For each case, the first line contains three integers N(1<=N<=100), M(1<=M<=100), K(1<=K<=100) . The meaning is described above.
Then N lines follow, each line contains 2 integers si and ti(0 <= si < ti <100000).
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Cij(1<=Cij<=100000) .
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Dij(1<=Dij<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Ei1i2(1<=Ei1j2<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Fi1i2(1 <= Fi1j2<=100000) .
Since the same candy will only be produced once, Eii and Fii are meaningless and will always be -1.
The input ends by N=0 M=0 K=0. Cases are separated with a blank line.
For each case, the first line contains three integers N(1<=N<=100), M(1<=M<=100), K(1<=K<=100) . The meaning is described above.
Then N lines follow, each line contains 2 integers si and ti(0 <= si < ti <100000).
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Cij(1<=Cij<=100000) .
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Dij(1<=Dij<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Ei1i2(1<=Ei1j2<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Fi1i2(1 <= Fi1j2<=100000) .
Since the same candy will only be produced once, Eii and Fii are meaningless and will always be -1.
The input ends by N=0 M=0 K=0. Cases are separated with a blank line.
Output
For each test case, if all of M candies can be produced, output the sum of minimum producing cost in a single line. Otherwise output -1.
Sample Input
3 2 1 4 7 2 4 8 9 4 4 3 3 3 3 2 8 12 3 14 6 -1 1 1 1 -1 1 1 1 -1 -1 5 5 5 -1 5 5 5 -1 1 1 2 1 5 5 5 -1 -1 0 0 0
Sample Output
11 -1
Hint
For the first example, the answer can be achieved in the following way:
Source
解题：最小费用最大流
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 510; 5 struct arc { 6 int to,flow,cost,next; 7 arc(int x = 0,int y = 0,int z = 0,int nxt = -1) { 8 to = x; 9 flow = y; 10 cost = z; 11 next = nxt; 12 } 13 } e[maxn*maxn]; 14 int head[maxn],p[maxn],d[maxn],S,T,tot,n,m,k; 15 void add(int u,int v,int flow,int cost) { 16 e[tot] = arc(v,flow,cost,head[u]); 17 head[u] = tot++; 18 e[tot] = arc(u,0,-cost,head[v]); 19 head[v] = tot++; 20 } 21 queue<int>q; 22 bool in[maxn]; 23 bool spfa() { 24 while(!q.empty()) q.pop(); 25 memset(p,-1,sizeof p); 26 memset(d,0x3f,sizeof d); 27 d[S] = 0; 28 q.push(S); 29 while(!q.empty()) { 30 int u = q.front(); 31 q.pop(); 32 in[u] = false; 33 for(int i = head[u]; ~i; i = e[i].next) { 34 if(e[i].flow && d[e[i].to] > d[u] + e[i].cost) { 35 d[e[i].to] = d[u] + e[i].cost; 36 p[e[i].to] = i; 37 if(!in[e[i].to]) { 38 in[e[i].to] = true; 39 q.push(e[i].to); 40 } 41 } 42 } 43 } 44 return p[T] > -1; 45 } 46 void solve() { 47 int ret = 0,flow = 0; 48 while(spfa()) { 49 int minF = INF; 50 for(int i = p[T]; ~i; i = p[e[i^1].to]) 51 minF = min(minF,e[i].flow); 52 for(int i = p[T]; ~i; i = p[e[i^1].to]) { 53 e[i].flow -= minF; 54 e[i^1].flow += minF; 55 } 56 ret += minF*d[T]; 57 flow += minF; 58 } 59 printf("%d ",flow < n?-1:ret); 60 } 61 int ss[maxn],tt[maxn],C[maxn][maxn],D[maxn][maxn],E[maxn][maxn],F[maxn][maxn]; 62 void Read() { 63 memset(head,-1,sizeof head); 64 for(int i = tot = 0; i < n; ++i) 65 scanf("%d%d",ss + i,tt + i); 66 for(int i = 0; i < n; ++i) 67 for(int j = 0; j < m; ++j) 68 scanf("%d",C[i] + j); 69 for(int i = 0; i < n; ++i) 70 for(int j = 0; j < m; ++j) 71 scanf("%d",D[i] + j); 72 for(int i = 0; i < n; ++i) 73 for(int j = 0; j < n; ++j) 74 scanf("%d",E[i] + j); 75 for(int i = 0; i < n; ++i) 76 for(int j = 0; j < n; ++j) 77 scanf("%d",F[i] + j); 78 } 79 int main() { 80 while(scanf("%d%d%d",&n,&m,&k),n||m||k) { 81 Read(); 82 S = 2*n + m; 83 T = S + 1; 84 for(int i = 0; i < n; ++i) { 85 add(S,i,1,0); 86 add(i + n,T,1,0); 87 } 88 for(int i = 0; i < m; ++i) 89 add(n + n + i,T,1,0); 90 for(int i = 0; i < n; ++i) 91 for(int j = 0; j < m; ++j) { 92 if(C[i][j] >= tt[i]) continue; 93 int cost = D[i][j]; 94 if(C[i][j] > ss[i]) cost += (C[i][j] - ss[i])*k; 95 add(i,2*n + j,1,cost); 96 } 97 for(int i = 0; i < n; ++i) 98 for(int j = 0; j < n; ++j) { 99 if(i == j) continue; 100 int ctime = tt[i] + E[i][j]; 101 if(ctime >= tt[j]) continue; 102 int cost = F[i][j]; 103 if(ctime > ss[j]) cost += k*(ctime - ss[j]); 104 add(j,i + n,1,cost); 105 } 106 solve(); 107 } 108 return 0; 109 }