題目鏈接

? ?本題是2001年icpc世界總決賽的G題

題意

? ?早期的多程序操作系統(tǒng)常把所有的可用內(nèi)存劃分成一些大小固定的區(qū)域，不同的區(qū)域一般大小不同，而所有區(qū)域的大小之和為可用內(nèi)存的大小。給定一些程序，操作系統(tǒng)需要給每個程序分配一個區(qū)域，使得它們可以同時執(zhí)行?？墒敲總€程序的運行時間可能和它所占有的內(nèi)存區(qū)域大小有關(guān)，因此調(diào)度并不容易。
? ?編程計算最優(yōu)的內(nèi)存分配策略，即給定m個區(qū)域的大小和n個程序在各種內(nèi)存環(huán)境下的運行時間，找出一個調(diào)度方案，使得平均回轉(zhuǎn)時間（即平均結(jié)束時刻）盡量小。具體來說，你需要給每個程序分配一個區(qū)域，使得沒有兩個程序在同一時間運行在同一個內(nèi)存區(qū)域中，而所有程序分配的區(qū)域大小都不小于該程序的最低內(nèi)存需求。程序?qū)?nèi)存的需求不會超過最大內(nèi)存塊的大小。

輸入格式

? ?輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行為正整數(shù)m 和n，即區(qū)域的個數(shù)和程序的個數(shù)（1≤m≤10, 1≤n≤50）。下一行包含m個正整數(shù)，即各內(nèi)存區(qū)域的大小。以下n行描述每個程序在各種內(nèi)存大小中的執(zhí)行時間，其中第一個整數(shù)為情況總數(shù)k（k≤10），然后是k對整數(shù)s1, t1, s2, t2, …, sk, tk，滿足si<si+1。當(dāng)內(nèi)存不足s1 時程序無法運行；當(dāng)內(nèi)存大小s滿足si≤s＜si+1時運行時間為ti；如果內(nèi)存至少為sk，運行時間為tk。輸入結(jié)束標(biāo)志為m=n=0。

輸出格式

? ?對于每組數(shù)據(jù)，輸出最小平均回轉(zhuǎn)時間和調(diào)度方案。如果有多組解，任意輸出一組即可。

分析

? ?這道題的建模極為經(jīng)典！《訓(xùn)練指南》題解：

? ?先來看一個內(nèi)存區(qū)域的情況。假設(shè)在這個內(nèi)存區(qū)域按順序執(zhí)行的k 個程序的運行時間分別為t1, t2, t3, …, tk，那么第i個程序的回轉(zhuǎn)時間為ri=t1+t2+…+ti，所有程序的回轉(zhuǎn)時間之和等于r=kt1+(k-1)t2+(k-2)t3+…+2tk-1+tk。換句話說，如果程序i 是內(nèi)存區(qū)域j的倒數(shù)第p個執(zhí)行的程序，則它對于總回轉(zhuǎn)時間的“貢獻值”為pTi,j，其中Ti,j為程序i 在內(nèi)存區(qū)域j中的運行時間。
? ?這樣一來，算法就比較明顯了。構(gòu)造二分圖G，X 結(jié)點為n個程序，Y結(jié)點為n×m個“位置”，其中位置(j,p)表示第j個內(nèi)存區(qū)域的倒數(shù)第p個執(zhí)行的程序。每個X結(jié)點i和Y結(jié)點(j,p)連有一條權(quán)為pTi,j的邊，然后求最小權(quán)匹配即可。注意，并不是每個匹配都對應(yīng)一個合法方案（比如，一個區(qū)域不能只有倒數(shù)第一個程序而沒有倒數(shù)第二個程序），但最佳匹配一定對應(yīng)一個合法方案（想一想，為什么）。

? ?下面就想一下這樣做的正確性：
? ?題解采用了倒數(shù)第p個這樣的設(shè)定，并且對應(yīng)邊權(quán)pTi,j中Ti,j一定是一個定值，那么自然是p越小越好。所以是先有了倒數(shù)第一才會有倒數(shù)第二，而不會只有倒數(shù)第一，沒有倒數(shù)第二，又有倒數(shù)第三的不符合現(xiàn)實的情況（這在其他非最大權(quán)的二分圖最大匹配有可能出現(xiàn)）。 二分圖最大權(quán)（權(quán)其實取負(fù)了）匹配避免開了這種不符合現(xiàn)實的情況， 所以一定是一個合法方案。
? ? 最后再提一點，二分圖最大權(quán)匹配，并一定要通過加點將X點集和Y點集的數(shù)量湊成相同再求最佳完美匹配，不加點的做法參見AC代碼。

AC 代碼

#include <iostream>
#include <iomanip>
using namespace std;#define INF 1000000000
#define M 11
#define N 51
int x[N][3], mem[M], a[M], c[M], w[N][M][N], slack[M][N], lx[N], ly[M][N], p[M][N], m, n, kase = 0; bool s[N], t[M][N];bool match(int i) {s[i] = true;for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) if (!t[j][k]) {int d = lx[i] + ly[j][k] - w[i][j][k];if (d == 0) {t[j][k] = true;if (!p[j][k] || match(p[j][k])) {p[j][k] = i;return true;}} else slack[j][k] = min(slack[j][k], d);}return false;
}void km() {for (int i=1; i<=n; ++i) lx[i] = -INF;for (int i=1; i<=m; ++i) for (int j=1; j<=n; ++j) p[i][j] = ly[i][j] = 0;for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) lx[i] = max(lx[i], w[i][j][k]);for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) slack[j][k] = INF;while (true) {for (int j=1; j<=n; ++j) s[j] = false;for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) t[j][k] = false;if (match(i)) break;int a = INF;for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) if (!t[j][k]) a = min(a, slack[j][k]);for (int j=1; j<=n; ++j) if (s[j]) lx[j] -= a;for (int j=1; j<=m; ++j) for (int k=1; k<=n; ++k) t[j][k] ? ly[j][k] += a : slack[j][k] -= a;}}
}void solve() {for (int i=1; i<=m; ++i) cin >> mem[i];for (int i=1; i<=n; ++i) {int k; cin >> k;for (int j=k; j>0; --j) cin >> a[j] >> c[j];for (int j=1, p; j<=m; ++j) {for (p=1; p<=k; ++p) if (mem[j] >= a[p]) {for (int k=1; k<=n; ++k) w[i][j][k] = -c[p]*k;break;}if (p > k) for (int k=1; k<=n; ++k) w[i][j][k] = -INF;}}km();int s = 0;for (int i=1; i<=n; ++i) s -= lx[i];for (int i=1; i<=m; ++i) for (int j=1; j<=n; ++j) s -= ly[i][j];for (int i=1, j; i<=m; ++i) if (p[i][1]) {for (int k=1; k<=n; ++k) if (p[i][k]) j = k;for (int k=j, t=0, y; k>0; --k) x[y = p[i][k]][0] = i, x[y][1] = t, x[y][2] = (t -= w[y][i][k]/k);}cout << "Case " << ++kase << endl << "Average turnaround time = " << s/double(n) << endl;for (int i=1; i<=n; ++i)cout << "Program " << i << " runs in region " << x[i][0] << " from " << x[i][1] << " to " << x[i][2] << endl;cout << endl;
}int main() {cout << fixed << setprecision(2);while (cin >> m >> n && m) solve();return 0;
}