【题意】：有n个人按照从1到m的顺序访问m个地方，每个人都可以不去或中途退出，但是如果退出了就不能再去后面的地方了。每个人去每个地方都有对应的收益和花费，n个人里任意两个人一起去同一个地方会有额外收益，如果多个人一起则额外收益为对任意两人的额外收益求和。现在求这n个人访问m个地方的收益+额外额外收益-花费的最大值。
【题解】：构图：首先对于m个地方，每个拆成n个点，这样n×m个点分别表示每个人访问每个地方，每个点的权就是这个人去对应地方的收益-花费，然后点权为正的连源，负的连汇，对于从2到m的点，每个点向它前一个点连一条容量无穷的边，表示访问该点前要先访问它前一个点。然后对于人和人间的额外收益，把每两个人间的边作为一个点，与源相连，容量为额外收益大小，然后如果这个点代表了a和b一起访问c点，则从这个点向表示a访问c和b访问c的两个点连容量为无穷的边。
【代码】：
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 }