首页 > 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


,
  1. 你这套无知加无耻的把戏是当年老毛玩剩下的,还敢拿出来丢人现眼?你怀念个人崇拜只能满足你的愿望把你送到北朝鲜,让你当奴才当个够?不愿意去?就是要借助鼓吹个人迷信干坏事。

  2. 你这个说法就过了,这么大的孩子心智不成熟,价值观尚未成型,并不能完全顾及到很多方面。 做错了事情也未必能意识到是怎么一个情况,所以说家长事后的态度就很重要了,道歉很合理也很必要,这意味着家长是明事理的,会对孩子进行教育,为孩子树立正确的价值观。讲道理,熊

  3. 请教下万戈,我的博客最近经常 无法显示,先是可以显示标题,网站内容是空白一片,然后刷新提示错误 15 (net::ERR_SOCKET_NOT_CONNECTED):未知错误。再刷新就是 错误 101 (net::ERR_CONNECTION_RESET

  4. 请教下万戈,我的博客最近经常 无法显示,先是可以显示标题,网站内容是空白一片,然后刷新提示错误 15 (net::ERR_SOCKET_NOT_CONNECTED):未知错误。再刷新就是 错误 101 (net::ERR_CONNECTION_RESET

  5. 请教下万戈,我的博客最近经常 无法显示,先是可以显示标题,网站内容是空白一片,然后刷新提示错误 15 (net::ERR_SOCKET_NOT_CONNECTED):未知错误。再刷新就是 错误 101 (net::ERR_CONNECTION_RESET

  6. 请教下万戈,我的博客最近经常 无法显示,先是可以显示标题,网站内容是空白一片,然后刷新提示错误 15 (net::ERR_SOCKET_NOT_CONNECTED):未知错误。再刷新就是 错误 101 (net::ERR_CONNECTION_RESET

  7. 原单■TISSOT(天梭)PRADA(普拉达)Stella Nina McCartney(斯特拉●麦卡特尼)JACK WOLFSKIN(狼爪)Versace(范思哲)Vacheron Constantin(江诗丹顿)ZIJINMOKA(紫金魔卡)hTtP://7493.shechipin.gq