首页 > ACM题库 > HDU-杭电 > HDU 4780-Candy Factory-图-[解题报告]HOJ
2015
09-17

HDU 4780-Candy Factory-图-[解题报告]HOJ

Candy Factory

问题描述 :

  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 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.

输出:

  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.

样例输入:

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

样例输出:

11
-1

Hint
For the first example, the answer can be achieved in the following way:
Tower Defense
In the picture, S i represents setting up time for candy i, A i represents changing time for candy i and P i represents producing time for candy i . So the total cost includes:   setting up machine 1 for candy 1, costs 2   setting up machine 2 for candy 2, costs 3   changing state from candy 2 to candy 3, costs 5   late start of candy 2, costs 1

题意:M个工厂生产N个糖果,现场过的人很少,但这道费用流本身并不是很难。

建图:我的建图是,每个糖果要么从初始状态转移过来,要么从其他糖果生产完的状态转移过来,同时拆点保证每个糖果只能生产一次。

另外看了杨神的建图,复杂度一样,但是他的抽象的更好,直接就是选择来源,这也是一般费用流的想法。

贴一下他的代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 510;
const int M = 1000010;
const int INF = 0x7f7f7f7f;

struct Edge {
    int v, cap, cost, next;
    Edge() {}
    Edge(int a, int b, int c, int d)
    :v(a), cap(b), cost(c), next(d) {}
}e[M];
int head[N], sz;
int dis[N], pre[N], cur[N];
bool inq[N];
queue<int> q;

void graphinit() {
    memset(head, -1, sizeof(head));
    sz = 0;
}
void addedge(int u, int v, int cp, int ct) {
//printf("%d %d %d %d\n", u, v, cp, ct);
    e[sz] = Edge(v, cp, ct, head[u]);
    head[u] = sz++;
    e[sz] = Edge(u, 0, -ct, head[v]);
    head[v] = sz++;
}
pair<int, int> mcmf(int s, int t) {
    int mc = 0, mf = 0;
    while (true) {
        memset(pre, -1, sizeof(pre));
        memset(inq, 0, sizeof(inq));
        memset(dis, 0x7f, sizeof(dis));
        dis[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].v;
                if (e[i].cap > 0 && dis[v] > dis[u] + e[i].cost) {
                    dis[v] = dis[u] + e[i].cost;
                    pre[v] = u; cur[v] = i;
                    if (!inq[v]) { inq[v] = true; q.push(v); }
                }
            }
        }
        if (pre[t] == -1) break;
        int aug = INF;
        for (int i = t; i != s; i = pre[i])
            aug = min(aug, e[cur[i]].cap);
        mf += aug;
        mc += dis[t] * aug;
        for (int i = t; i != s; i = pre[i]) {
            e[cur[i]].cap -= aug;
            e[cur[i] ^ 1].cap += aug;
        }
    }
    return make_pair(mf, mc);
}

const int MAXN = 110;
int n, m, k;
int candy_s[MAXN], candy_t[MAXN];
int start_time[MAXN][MAXN], start_cost[MAXN][MAXN];
int change_time[MAXN][MAXN], change_cost[MAXN][MAXN];

void read_matrix(int a[MAXN][MAXN], int n, int m) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
}
void work() {
    for (int i = 0; i < n; i++)
        scanf("%d%d", candy_s + i, candy_t + i);
    read_matrix(start_time, n, m);
    read_matrix(start_cost, n, m);
    read_matrix(change_time, n, n);
    read_matrix(change_cost, n, n);

    graphinit();
    int ss = 2 * n + m, tt = ss + 1;
    for (int i = 0; i < n; i++)
        addedge(ss, i, 1, 0);
    for (int i = 0; i < m; i++)
        addedge(i + n, tt, 1, 0);
    for (int i = 0; i < n; i++)
        addedge(i + n + m, tt, 1, 0);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (start_time[i][j] >= candy_t[i]) continue;
            int cost = start_cost[i][j];
            if (start_time[i][j] > candy_s[i])
                cost += k * (start_time[i][j] - candy_s[i]);
            addedge(i, j + n, 1, cost);
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (i != j) {
            int dt = candy_t[i] + change_time[i][j];
            if (dt >= candy_t[j]) continue;
            int cost = change_cost[i][j];
            dt -= candy_s[j];
            if (dt > 0)
                cost += k * dt;
            addedge(j, i + n + m, 1, cost);
        }

    pair<int, int> ans = mcmf(ss, tt);
    if (ans.first < n) puts("-1");
    else printf("%d\n", ans.second);
}
int main() {
//freopen("../data.in", "r", stdin);
    while (scanf("%d%d%d", &n, &m, &k), n || m || k) {
        work();
    }
    return 0;
}

参考:http://blog.csdn.net/qq564690377/article/details/16829939


,