2014-07-23

UVa 11613 - Acme Corporation

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

Wile E. Coyote is back. He is back in the business. The business of capturing the road runner. Being the most loyal customer to the Acme Corporation, they are hoping to do some great business with him. Although, Acme makes literally every kinds of devices, all of them has a similarity, that has been kept secret for ages. All of their products use a secret element “element X” (this is kept so secret that, only you and the Acme people know about this). The decision makers of the Acme Corp. has already estimated the maximum amount of element X that can be used into manufacture every month.

For month i, the per unit manufacturing cost of “element X” is mi, and at most ni units can be produced. Moreover, the selling price for “element X” for that month is pi. One more thing is that, element X older than Ei months can not be used. But good thing is that, they can store any amount of element X in their inventory (it’s the Acme Corp, they can make anything :) ). Now, Acme Corporation wants to know how much element X should be produced and sold, to make the highest amount of profit.

Input

l First line contains T, the number of test cases.

l For each test case

u First line contains two integers M and I, the number of months to consider and the cost of storing per unit of element X per month in the inventory.

u Each of the next M lines describe the parameters for each month

· The ith line contains 5 integers, mi, ni, pi, si, Ei, where mi is the per unit manufacturing cost for month i, ni is the maximum amount that can be manufactured in this month, pi is the selling price for that month(per unit), si is the maximum amount that can be sold that month, and Ei is the maximum time,element X manufactured on month i, can be stored in the inventory. For example, if for month 1, E1 = 3, the elements produced in month 1 can be sold in months 1, 2, 3 and 4. But it can not be sold in month 5.

Output

For each test case, output the case number and the maximum amount of profit, Acme Corporation can make. Note that, you have to think of only M months. If any amount of element X is stored in the inventory after this period, are completely ignored. For formatting, see the sample input and output.

Sample Input

1
2 2
2 10 3 20 2
10 100 7 5 2

Output for Sample Input

1	Case 1: 20

Solution

題目描述：

這個工廠，每個月會生產商品，在每個月中，每一個商品會有其生產成本、該月最大生產量、該月最大銷售量、產品的保存期限。

然而沒有銷售的的商品，將會放置於倉庫，每個月的保管成本為 I。求最大獲益金額為何。

題目解法：

將銷售金額與負號，最小費用流即最大獲益。

source - product - sell - sink，將每一個月的訊息拆成兩個節點，生產的數量和銷售的情況，並且根據保存期限，將該月的生產數量拉至可預期的銷售時間，並且同時扣除保管成本。

 
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
    int x, y;
    long long cap, cost;// x->y, v
    int next;
} edge[262144];
int e, head[512], prev[512], record[512], inq[512];
long long dis[512];
void addEdge(int x, int y, long long cap, long long cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
long long mincost(int s, int t) {
    long long mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        int oo = dis[0];
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    prev[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] > 0)	break;
        flow = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int testcase, cases = 0;
    int M, I;
    int pm[128], pn[128], pp[128], ps[128], pe[128];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d", &M, &I);
    	e = 0;
        memset(head, -1, sizeof(head));
        
        int source = 2 * M + 2, sink = source + 1;
        for(int i = 1; i <= M; i++)
        	scanf("%d %d %d %d %d", pm+i, pn+i, pp+i, ps+i, pe+i);
#define INF 0x3f3f3f3f
        for(int i = 1; i <= M; i++) {
        	addEdge(source, 2*i, pn[i], pm[i]);
        	for(int j = i; j <= min(i + pe[i], M); j++)
        		addEdge(2*i, 2*j+1, INF, (j - i) * I);
        	addEdge(2*i+1, sink, ps[i], -pp[i]);
        }
        
        printf("Case %d: %lld\n", ++cases, -mincost(source, sink));
    }
    return 0;
}

Morris' Blog