题目大意
给出一个长度为个，问最多能取出的数的权值和是多少。
思路
非常神的建图，本来想朴素费用流不过去学zkw费用流，结果朴素费用流跑的飞起。 利用一些辅助变量我们可以列出一些式子： 设数组一定是自然数。 保持第一个式子和最后一个式子不变，剩下的式子上下作差，得到如下的式子： ] 现在看就比较明显了，把第一个式子和最后一个式子分别看成是源点和汇点，，其他的式子和看成是点，变量有相关连的就连边，注意每个变量的原始意义。 每个式子拆成两半，等号表示流量守恒，左边表示流入，右边表示流出，费油就是读入的权值。之后就是最大费用最大流了。
CODE;int cnt, k;int src[MAXP];struct MinCostMaxFlow{int head[MAXP], total;int _next[MAXE], aim[MAXE], flow[MAXE], cost[MAXE];int f[MAXP], from[MAXP], p[MAXP];bool v[MAXP];MinCostMaxFlow():total(1) {}void Add(int x, int y, int f, int c) {_next[++total] = head[x];aim[total] = y;flow[total] = f;cost[total] = c;head[x] = total;}void Insert(int x, int y, int f, int c) {Add(x, y, f, -c);Add(y, x, 0, c);}bool SPFA() {static queue<int> q;while(!q.empty()) q.pop();memset(f, 0x3f, sizeof(f));memset(v, false, sizeof(v));f[SS] = 0;q.push(SS);while(!q.empty()) {int x = q.front(); q.pop();v[x] = false;for(int i = head[x]; i; i = _next[i])if(flow[i] && f[aim[i]] > f[x] + cost[i]) {f[aim[i]] = f[x] + cost[i];if(!v[aim[i]])v[aim[i]] = true, q.push(aim[i]);from[aim[i]] = x;p[aim[i]] = i;}}return f[TT] != INF;}int EdmondsKarp() {int re = 0;while(SPFA()) {int max_flow = INF;for(int i = TT; i != SS; i = from[i])max_flow = min(max_flow, flow[p[i]]);for(int i = TT; i != SS; i = from[i]) {flow[p[i]] -= max_flow;flow[p[i]^1] += max_flow;}re += max_flow * f[TT];}return re;}}solver;int main(){cin >> cnt >> k;for(int i = 1; i <= cnt * 3; ++i)scanf(“%d”, &src[i]);solver.Insert(SS, S, k, 0);solver.Insert(T, TT, k, 0);for(int i = 2; i <= cnt + 1; ++i)solver.Insert(S, i, 1, src[i – 1]);for(int i = cnt + 2; i <= cnt * 2 + 1; ++i)solver.Insert(i – cnt, i, 1, src[i – 1]);for(int i = cnt + 2; i <= cnt * 2 + 1; ++i)solver.Insert(i, (cnt << 1) + 2, 1, src[i – 1 + cnt]);for(int i = 2; i <= cnt * 2 + 2; ++i)solver.Insert(i – 1, i, k, 0);cout << -solver.EdmondsKarp() << endl;return 0;}
或许是某个未开发的荒凉小岛，或许是某座闻名遐迩的文化古城。
