【題意】：切水果游戲。給出n個水果，每個水果有對應(yīng)的分?jǐn)?shù)，規(guī)定連續(xù)m個水果之間最多能切掉k個，求能夠切得的最大分?jǐn)?shù)。

【題解】：一道論文題。發(fā)現(xiàn)網(wǎng)絡(luò)流確實強(qiáng)大，可以解決很多問題。
               這題解法是最大費用流，看到了論文的構(gòu)圖，發(fā)現(xiàn)超級強(qiáng)大。
               構(gòu)圖：
               把每個水果拆成兩個點 i 和 i’，連邊 i -> i’，容量為1，費用為切掉這個水果的分?jǐn)?shù)；
               加入一個源點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 }