【题意】:切水果游戏。给出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, -1sizeof(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, 00);
31 }
32 
33 bool spfa() {
34     head = tail = 0;
35     memset(visit, falsesizeof(visit));
36     memset(p, -1sizeof(p));
37     memset(low, 0sizeof(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 + 10, 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 }