2015
09-17

# 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:

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


#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 dis[N], pre[N], cur[N];
bool inq[N];
queue<int> q;

void graphinit() {
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]);
e[sz] = Edge(u, 0, -ct, head[v]);
}
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);

graphinit();
int ss = 2 * n + m, tt = ss + 1;
for (int i = 0; i < n; i++)
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;
}

,
1. 管理员，你妈的逼太松了，不够爽啊！不过水倒是挺多的额！！管理员，你妈的逼太松了，不够爽啊！不过水倒是挺多的额！！管理员，你妈的逼太松了，不够爽啊！不过水倒是挺多的额！！管理员，你妈的逼太松了，不够爽啊！不过水倒是挺多的额！！管理员，你妈的逼太松了，不够爽

2. 这种都是利用人贪财的心理，言语和物质上的蛊惑，你表姐是以为那些外币值钱，你舅舅是因为觉的对方有实物做抵押，因为他们已经盘算好自己不仅不会亏，还会赚，所以才会被骗。总之都是财迷心窍所致。

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

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

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

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

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