【题意】：切水果游戏。给出n个水果，每个水果有对应的分数，规定连续m个水果之间最多能切掉k个，求能够切得的最大分数。
【题解】：一道论文题。发现网络流确实强大，可以解决很多问题。
这题解法是最大费用流，看到了论文的构图，发现超级强大。
构图：
把每个水果拆成两个点 i 和 i’，连边 i -> i’，容量为1，费用为切掉这个水果的分数；
加入一个源点s，连边s -> i，容量为inf，费用为0；
加入一个汇点t，连边 i’ -> t，容量为inf，费用为0；
连边i -> i + 1，容量为inf，费用为0；
连边i' -> i + m，容量为inf，费用为0。
最后，限定最多增广k次即可，最大费用即为答案。这题时限卡得比较紧，最好不要用stl的queue。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 2500
6 #define maxm 1000000
7 const int inf = 1 << 30;
8 int eh[maxn], p[maxn], low[maxn], tot, dist[maxn];
9 int s, t, n, m, k;
10 int ans, anscost;
11 int val[maxn];
12 bool visit[maxn];
13 int que[1000000], head, tail;
14 struct Edge {
15 int u, v, cost, cap, flow, next;
16 }et[maxm];
17
18 void init() {
19 tot = 0;
20 memset(eh, -1, sizeof(eh));
21 }
22
23 void add(int u, int v, int cost, int cap, int flow) {
24 Edge e = {u, v, cost, cap, flow, eh[u]};
25 et[tot] = e;
26 eh[u] = tot++;
27 }
28
29 void addedge(int u, int v, int cost, int cap) {
30 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
31 }
32
33 bool spfa() {
34 head = tail = 0;
35 memset(visit, false, sizeof(visit));
36 memset(p, -1, sizeof(p));
37 memset(low, 0, sizeof(low));
38 for(int i = 0; i < maxn; i++) dist[i] = -inf;
39 visit[s] = true, low[s] = inf, dist[s] = 0;
40 que[tail++] = s;
41 while(head < tail) {
42 int u = que[head++];
43 visit[u] = false;
44 for(int i = eh[u]; i != -1; i = et[i].next) {
45 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
46 if(cap - flow && dist[u] + cost > dist[v]) {
47 dist[v] = dist[u] + cost;
48 p[v] = i;
49 low[v] = min(low[u], cap - flow);
50 if(!visit[v]) {
51 que[tail++] = v;
52 visit[v] = true;
53 }
54 }
55 }
56 }
57 return dist[t] != -inf;
58 }
59
60 void costflow() {
61 ans = anscost = 0;
62 while(ans < k && spfa()) {
63 int x = p[t];
64 ans += low[t];
65 anscost += low[t] * dist[t];
66 while(x != -1) {
67 et[x].flow += low[t];
68 et[x^1].flow -= low[t];
69 x = p[et[x].u];
70 }
71 }
72 }
73
74 int main() {
75 while(~scanf("%d%d%d", &n, &m, &k)) {
76 init();
77 m = min(n, m);
78 int sum = 0;
79 s = 0, t = 2 * n + 1;
80 for(int i = 1; i <= n; i++) {
81 scanf("%d", &val[i]);
82 sum += val[i];
83 addedge(s, i, 0, inf);
84 addedge(i, i + n, val[i], 1);
85 addedge(i + n, t, 0, inf);
86 if(i + 1 <= n) addedge(i, i + 1, 0, inf);
87 if(i + m <= n) addedge(i + n, i + m, 0, inf);
88 }
89 if(m == k) {
90 printf("%d\n", sum);
91 continue;
92 }
93 costflow();
94 printf("%d\n", anscost);
95 }
96 return 0;
97 }