【題意】：有 M 個(gè)豬圈（M ≤ 1000），每個(gè)豬圈里初始時(shí)有若干頭豬。開始所有豬圈都是關(guān)閉的。依次來了 N 個(gè)顧客（N ≤ 100），每個(gè)顧客分別會(huì)打開指定的幾個(gè)豬圈，從中買若干頭豬。每個(gè)顧客分別都有他能夠買的數(shù)量的上限。每個(gè)顧客走后，他打開的那些豬圈中的豬，都可以被任意地調(diào)換到其它開著的豬圈里，然后所有豬圈重新關(guān)上。 問總共最多能賣出多少頭豬。
【題解】：舉個(gè)例子來說。有 3 個(gè)豬圈，初始時(shí)分別有 3、 1 和 10 頭豬。依次來了 3 個(gè)顧客，第一個(gè)打開 1 號 和 2 號豬圈，最多買 2 頭；第二個(gè)打開 1 號 和 3 號豬圈，最多買 3 頭；第三個(gè)打開 2 號豬圈，最多買 6 頭。那么，最好的可能性之一就是第一個(gè)顧客從 1 號圈買 2 頭，然后把 1 號圈剩下的 1 頭放到 2 號圈；第二個(gè)顧客從 3 號圈買 3 頭；第三個(gè)顧客從 2 號圈買 2 頭。總共賣出 2 + 3 + 2 = 7 頭。□
不難想像，這個(gè)問題的網(wǎng)絡(luò)模型可以很直觀地構(gòu)造出來。就拿上面的例子來說，可以構(gòu)造出圖1所示的模型（圖中凡是沒有標(biāo)數(shù)字的邊，容量都是 +∞）：
- 三個(gè)顧客，就有三輪交易，每一輪分別都有 3 個(gè)豬圈和 1 個(gè)顧客的節(jié)點(diǎn)。
- 從源點(diǎn)到第一輪的各個(gè)豬圈各有一條邊，容量就是各個(gè)豬圈里的豬的初始數(shù)量。
- 從各個(gè)顧客到匯點(diǎn)各有一條邊，容量就是各個(gè)顧客能買的數(shù)量上限。
- 在某一輪中，從該顧客打開的所有豬圈都有一條邊連向該顧客，容量都是 +∞。
- 最后一輪除外，從每一輪的 i 號豬圈都有一條邊連向下一輪的 i 號豬圈，容量都是 +∞，表示這一輪剩下的豬可以留到下一輪。
- 最后一輪除外，從每一輪被打開的所有豬圈，到下一輪的同樣這些豬圈，兩兩之間都要連一條邊，表示它們之間可以任意流通。
圖 1
不難想像，這個(gè)網(wǎng)絡(luò)模型的最大流量就是最多能賣出的數(shù)量。圖中最多有 2 + N + M × N ≈ 100,000 個(gè)節(jié)點(diǎn)。□
這個(gè)模型雖然很直觀，但是節(jié)點(diǎn)數(shù)太多了，計(jì)算速度肯定會(huì)很慢。其實(shí)不用再想別的算法，就讓我們繼續(xù)上面的例子，用合并的方法來簡化這個(gè)網(wǎng)絡(luò)模型。
首先，最后一輪中沒有打開的豬圈就可以從圖中刪掉了，也就是中圖2
紅色的部分，顯然它們對整個(gè)網(wǎng)絡(luò)的流量沒有任何影響。
圖 2
接著，看
圖 2 中
藍(lán)色的部分。根據(jù)我總結(jié)出的以下幾個(gè)規(guī)律，可以把這 4 個(gè)點(diǎn)合并成一個(gè)：
規(guī)律 1. 如果幾個(gè)節(jié)點(diǎn)的流量的
來源完全相同，則可以把它們合并成一個(gè)。
規(guī)律 2. 如果幾個(gè)節(jié)點(diǎn)的流量的
去向完全相同，則可以把它們合并成一個(gè)。
規(guī)律 3. 如果從點(diǎn) u 到點(diǎn) v 有一條容量為 +∞ 的邊，并且 u 是 v 的
唯一流量
來源，或者 v 是 u 的
唯一流量
去向，則可以把 u 和 v 合并成一個(gè)節(jié)點(diǎn)。
根據(jù)規(guī)律1，可以把
藍(lán)色部分右邊的 1、 2 號節(jié)點(diǎn)合并成一個(gè)；根據(jù)規(guī)律2，可以把
藍(lán)色部分左邊的 1、 2 號節(jié)點(diǎn)合并成一個(gè)；最后，根據(jù)規(guī)律3，可以把
藍(lán)色部分的左邊和右邊（已經(jīng)分別合并成了一個(gè)節(jié)點(diǎn)）合并成一個(gè)節(jié)點(diǎn)。于是，圖2被簡化成了圖3的樣子。也就是說，最后一輪除外，每一輪被打開的豬圈和下一輪的同樣這些豬圈都可以被合并成一個(gè)點(diǎn)。
圖 3
接著，根據(jù)，圖3中的藍(lán)色節(jié)點(diǎn)、2 號豬圈和 1 號顧客這三點(diǎn)可以合并成一個(gè)；圖3中的兩個(gè) 3 號豬圈和 2 號顧客也可以合并成一個(gè)點(diǎn)。當(dāng)然，如果兩點(diǎn)之間有多條同向的邊，則這些邊可以合并成一條，容量相加，這個(gè)道理很簡單，就不用我多說了。最終，上例中的網(wǎng)絡(luò)模型被簡化成了圖4 的樣子。
圖 4
讓我們從圖4中重新總結(jié)一下構(gòu)造這個(gè)網(wǎng)絡(luò)模型的規(guī)則：
- 每個(gè)顧客分別用一個(gè)節(jié)點(diǎn)來表示。
- 對于每個(gè)豬圈的第一個(gè)顧客，從源點(diǎn)向他連一條邊，容量就是該豬圈里的豬的初始數(shù)量。如果從源點(diǎn)到一名顧客有多條邊，則可以把它們合并成一條，容量相加。
- 對于每個(gè)豬圈，假設(shè)有 n 個(gè)顧客打開過它，則對所有整數(shù) i ∈ [1, n)，從該豬圈的第 i 個(gè)顧客向第 i + 1 個(gè)顧客連一條邊，容量為 +∞。
- 從各個(gè)顧客到匯點(diǎn)各有一條邊，容量是各個(gè)顧客能買的數(shù)量上限。
拿我們前面一直在講的例子來說：1 號豬圈的第一個(gè)顧客是 1 號顧客，所以從源點(diǎn)到 1 號顧客有一條容量為 3 的邊；1 號豬圈的第二個(gè)顧客是 2 號顧客，因此從 1 號顧客到 2 號顧客有一條容量為 +∞ 的邊；2 號豬圈的第一個(gè)顧客也是 1 號顧客，所以從源點(diǎn)到 1 號顧客有一條容量為 1 的邊，和之前已有的一條邊合并起來，容量變成 4；2 號豬圈的第二個(gè)顧客是 3 號顧客，因此從 1 號顧客到 3 號顧客有一條容量為 +∞ 的邊；3 號豬圈的第一個(gè)顧客是 2 號顧客，所以從源點(diǎn)到 2 號顧客有一條容量為 10 的邊。□
新的網(wǎng)絡(luò)模型中最多只有 2 + N = 102 個(gè)節(jié)點(diǎn)，計(jì)算速度就可以相當(dāng)快了。可以這樣理解這個(gè)新的網(wǎng)絡(luò)模型：對于某一個(gè)顧客，如果他打開了豬圈 h，則在他走后，他打開的所有豬圈里剩下的豬都有可能被換到 h 中，因而這些豬都有可能被 h 的下一個(gè)顧客買走。所以對于一個(gè)顧客打開的所有豬圈，從該顧客到各豬圈的下一個(gè)顧客，都要連一條容量為 +∞ 的邊。
在面對網(wǎng)絡(luò)流問題時(shí)，如果一時(shí)想不出很好的構(gòu)圖方法，不如先構(gòu)造一個(gè)最直觀，或者說最“硬來”的模型，然后再用合并節(jié)點(diǎn)和邊的方法來簡直化這個(gè)模型。經(jīng)過簡化以后，好的構(gòu)圖思路自然就會(huì)涌現(xiàn)出來了。這是解決網(wǎng)絡(luò)流問題的一個(gè)好方法。
【代碼】：
1 #include "iostream"
2 using namespace std;
3 #define maxn 500
4 #define maxm 50005
5 #define maxhouse 1005
6 const int INF = 99999999;
7 int s, t, house, ctm, tot;
8 int eh[maxn], pre[maxn], cur[maxn], gap[maxn], dist[maxn], a[maxn], hcap[maxhouse];
9 bool visit[maxhouse];
10
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 void init() {
16 tot = 0;
17 memset(eh, -1, sizeof(eh));
18 }
19
20 int min(int a, int b) {
21 return a < b ? a : b;
22 }
23
24 void add(int u, int v, int cap, int flow) {
25 Edge E = {u, v, cap, flow, eh[u]};
26 et[tot] = E;
27 eh[u] = tot++;
28 }
29
30 void addedge(int u, int v, int cap) {
31 add(u, v, cap, 0), add(v, u, 0, 0);
32 }
33
34 int isap(int s, int t, int n) {
35 int u, v, now;
36 memset(dist, 0, sizeof(dist));
37 memset(a, 0, sizeof(a));
38 for(u = 0; u <= n; u++) cur[u] = eh[u];
39 int maxflow = 0;
40 u = s, a[s] = INF, gap[0] = n;
41 while(dist[s] < n) {
42 for(now = cur[u]; now != -1; now = et[now].next)
43 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
44 break;
45 if(now != -1) {
46 cur[u] = pre[v] = now;
47 a[v] = min(a[u], et[now].cap - et[now].flow);
48 u = v;
49 if(u == t) {
50 for(; u != s; u = et[pre[u]].u) {
51 et[pre[u]].flow += a[t];
52 et[pre[u]^1].flow -= a[t];
53 }
54 maxflow += a[t], a[s] = INF;
55 }
56 } else {
57 if(--gap[dist[u]] == 0) break;
58 dist[u] = n;
59 cur[u] = eh[u];
60 for(now = eh[u]; now != -1; now = et[now].next)
61 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
62 dist[u] = dist[et[now].v] + 1;
63 gap[dist[u]]++;
64 if(u != s) u = et[pre[u]].u;
65 }
66 }
67 return maxflow;
68 }
69
70 int main() {
71 int i, j, cap, v, nkey;
72 memset(visit, false, sizeof(visit));
73 cin >> house >> ctm;
74 init();
75 s = 0, t = ctm + 1;
76 for(i = 1; i <= house; i++) {
77 cin >> hcap[i];
78 }
79 for(i = 1; i <= ctm; i++) {
80 cin >> nkey;
81 for(j = 1; j <= nkey; j++) {
82 cin >> v;
83 if(!visit[v]) {
84 addedge(s, i, hcap[v]);
85 visit[v] = true;
86 pre[v] = i;
87 }
88 else addedge(pre[v], i, INF);
89 }
90 cin >> cap;
91 addedge(i, t, cap);
92 }
93 cout << isap(s, t, t - s + 1) << endl;
94 return 0;
95 }