【題意】：有n個(gè)人按照從1到m的順序訪問m個(gè)地方，每個(gè)人都可以不去或中途退出，但是如果退出了就不能再去后面的地方了。每個(gè)人去每個(gè)地方都有對(duì)應(yīng)的收益和花費(fèi)，n個(gè)人里任意兩個(gè)人一起去同一個(gè)地方會(huì)有額外收益，如果多個(gè)人一起則額外收益為對(duì)任意兩人的額外收益求和。現(xiàn)在求這n個(gè)人訪問m個(gè)地方的收益+額外額外收益-花費(fèi)的最大值。
【題解】：構(gòu)圖：首先對(duì)于m個(gè)地方，每個(gè)拆成n個(gè)點(diǎn)，這樣n×m個(gè)點(diǎn)分別表示每個(gè)人訪問每個(gè)地方，每個(gè)點(diǎn)的權(quán)就是這個(gè)人去對(duì)應(yīng)地方的收益-花費(fèi)，然后點(diǎn)權(quán)為正的連源，負(fù)的連匯，對(duì)于從2到m的點(diǎn)，每個(gè)點(diǎn)向它前一個(gè)點(diǎn)連一條容量無窮的邊，表示訪問該點(diǎn)前要先訪問它前一個(gè)點(diǎn)。然后對(duì)于人和人間的額外收益，把每?jī)蓚€(gè)人間的邊作為一個(gè)點(diǎn)，與源相連，容量為額外收益大小，然后如果這個(gè)點(diǎn)代表了a和b一起訪問c點(diǎn)，則從這個(gè)點(diǎn)向表示a訪問c和b訪問c的兩個(gè)點(diǎn)連容量為無窮的邊。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 const int inf = 1 << 30;
6 #define maxn 2000
7 #define maxm 20000
8 int n, m, s, t;
9 int eh[maxn], pre[maxn], low[maxn], cur[maxn], cnt[maxn], dist[maxn], tot;
10 int cost[15], ins[15][15], bonus[15][15], sum;
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 void init() {
16 tot = sum = 0;
17 memset(eh, -1, sizeof(eh));
18 }
19
20 void add(int u, int v, int cap, int flow) {
21 Edge e = {u, v, cap, flow, eh[u]};
22 et[tot] = e;
23 eh[u] = tot++;
24 }
25
26 void addedge(int u, int v, int cap) {
27 add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29
30 int isap(int s, int t, int n) {
31 int u, v, now, flow = 0;
32 memset(cnt, 0, sizeof(cnt));
33 memset(low, 0, sizeof(low));
34 memset(dist, 0, sizeof(dist));
35 for(u = 0; u <= n; u++) cur[u] = eh[u];
36 u = s, low[s] = inf, cnt[0] = n;
37 while(dist[s] < n) {
38 for(now = cur[u]; now != -1; now = et[now].next)
39 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
40 if(now != -1) {
41 cur[u] = pre[v] = now;
42 low[v] = min(low[u], et[now].cap - et[now].flow);
43 u = v;
44 if(u == t) {
45 for(flow += low[t]; u != s; u = et[pre[u]].u) {
46 et[pre[u]].flow += low[t];
47 et[pre[u]^1].flow -= low[t];
48 }
49 }
50 } else {
51 if(--cnt[dist[u]] == 0) break;
52 dist[u] = n, cur[u] = eh[u];
53 for(now = eh[u]; now != -1; now = et[now].next)
54 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
55 dist[u] = dist[et[now].v] + 1;
56 cnt[dist[u]]++;
57 if(u != s) u = et[pre[u]].u;
58 }
59 }
60 return flow;
61 }
62
63 void build() {
64 s = 0, t = n * m + n * n * m + 1;
65 for(int i = 1; i <= n; i++) {
66 for(int j = 1; j <= m; j++) {
67 if(ins[i][j] > 0) {
68 addedge(s, (i - 1) * m + j, ins[i][j]);
69 sum += ins[i][j];
70 } else addedge((i - 1) * m + j, t, -ins[i][j]);
71 if(j > 1) addedge((i - 1) * m + j, (i - 1) * m + j - 1, inf);
72 }
73 }
74 for(int i = 1; i <= n; i++) {
75 for(int j = i + 1; j <= n; j++) {
76 for(int k = 1; k <= m; k++) {
77 addedge(s, n * m + ((i - 1) * n + j - 1) * m + k, bonus[i][j]);
78 addedge(n * m + ((i - 1) * n + j - 1) * m + k, (i - 1) * m + k, inf);
79 addedge(n * m + ((i - 1) * n + j - 1) * m + k, (j - 1) * m + k, inf);
80 sum += bonus[i][j];
81 }
82 }
83 }
84 }
85
86 int main() {
87 while(~scanf("%d%d", &n, &m)) {
88 if(!n && !m) break;
89 init();
90 for(int i = 1; i <= m; i++) scanf("%d", &cost[i]);
91 for(int i = 1; i <= n; i++) {
92 for(int j = 1; j <= m; j++) {
93 scanf("%d", &ins[i][j]);
94 ins[i][j] -= cost[j];
95 }
96 }
97 for(int i = 1; i <= n; i++)
98 for(int j = 1; j <= n; j++)
99 scanf("%d", &bonus[i][j]);
100 build();
101 int res = isap(s, t, t - s + 1);
102 if(res == sum) printf("STAY HOME\n");
103 else printf("%d\n", sum - res);
104 }
105 return 0;
106 }