題目鏈接

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

題意

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

輸入格式

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

輸出格式

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

分析

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

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

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