学姐的逛街计划
描述
doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.
偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.doc 很忧伤, 因为他还要陪学姐去逛街呢.
后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.
现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商.doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.可是, 究竟这个和最大能是多少呢?
格式
输入格式
第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.
第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数输出格式
输出只有一个整数, 表示可以取到的最大智商和.
样例1
样例输入1
5 314 21 9 30 11 8 1 20 29 23 17 27 7 8 35
样例输出1
195
限制
对于 20% 的数据, 1 <= n <= 12 , k = 3.
对于 70% 的数据, 1 <= n <= 40 .对于 100% 的数据, 1 <= n <= 200 , 1 <= k <= 10. 分析：
可以记第i天去不去逛街为a[i],第i天智商为val[i]；
设：
p[1] = a[1] + a[2] + …… + a[n] <= k；
p[2] = a[2] + a[3] + …… + a[n + 1] <= k
……
p[n * 2 + 1] = a[n * 2 + 1] + a[n * 2 + 2] + …… + a[3 * n] <= k
然后添加辅助变量y[i]，设q[i] = p[i] + y[i] = k
可得：
q[1] = p[1] +y[1] = k
q[2] = p[2] +y[2] = k
……
q[n * 2 + 1] = p[n * 2 + 1] +y[n * 2 + 1] = k
添加 辅助变量 q[0] = 0，q[n * 2 + 2] = 0
依次相减得到：
q[1] - q[0] = a[1] + a[2] + …… + a[n] + y[1] = k; ---- 1
q[2] - q[1] = a[n + 1] - a[1] + y[2] - y[1] = 0; ----2
q[3] - q[2] = a[n + 2] - a[2] + y[3] - y[2] = 0;----3
……
q[n * 2 + 2] - q[n * 2 + 1] = - a[n * 2 + 1] - a[n * 2 + 2] - …… - a[3 * n] - y[n * 2 + 1] = -k;-----n * 2 + 2
可以发现每一个变量都在等式中出现了两次，并且一次为正，一次为负，正相对于网络流中的流量守恒，流进等于流出（实际流量即为变量的值）
于是我们可以把每个等式看成一个点。把源点和第一个点连流量为k，花费为0。汇点和最后一个点连流量为k，花费为0；
对于每一个a[i]把它在等式中为正的点连向它在等式中为负的点，流量为1，花费为-val[i]。（因为求最大费用最大流，花费取负数后答案再倒回来就行）
对于每一个y[i]把它在等式中为正的点连向它在等式中为负的点，流量为k，花费为0。
然后求一遍最小费用最大流，答案取相反数（这样变成了最大费用最大流），就为我们要的答案。
贴上AC代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int N = 1e4; 7 const int M = 4e5; 8 const int INF = 0x3f3f3f3f; 9 using namespace std; 10 struct Edge 11 { 12 int from, to, cap, flow, cost, next; 13 }; 14 Edge edge[M]; 15 int head[N], inde,pre[N], dist[N]; 16 bool vis[N]; 17 int n,k; 18 void init() 19 { 20 inde = 0; 21 memset(head, -1, sizeof(head)); 22 } 23 void AddEdge(int u, int v, int w, int c) 24 { 25 Edge E1 = {u, v, w, 0, c, head[u]}; 26 edge[inde] = E1; 27 head[u] = inde++; 28 Edge E2 = {v, u, 0, 0, -c, head[v]}; 29 edge[inde] = E2; 30 head[v] = inde++; 31 } 32 bool SPFA(int s, int t) 33 { 34 queue Q; 35 memset(dist, INF, sizeof(dist)); 36 memset(vis, false, sizeof(vis)); 37 memset(pre, -1, sizeof(pre)); 38 dist[s] = 0; 39 vis[s] = true; 40 Q.push(s); 41 while(!Q.empty()) 42 { 43 int u = Q.front(); 44 Q.pop(); 45 vis[u] = false; 46 for(int i = head[u]; i != -1; i = edge[i].next) 47 { 48 Edge E = edge[i]; 49 if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow) 50 { 51 dist[E.to] = dist[u] + E.cost; 52 pre[E.to] = i; 53 if(!vis[E.to]) 54 { 55 vis[E.to] = true; 56 Q.push(E.to); 57 } 58 } 59 } 60 } 61 return pre[t] != -1; 62 } 63 void MCMF(int s, int t, int &cost, int &flow) 64 { 65 flow = 0; 66 cost = 0; 67 while(SPFA(s, t)) 68 { 69 int Min = INF; 70 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 71 { 72 Edge E = edge[i]; 73 Min = min(Min, E.cap - E.flow); 74 } 75 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 76 { 77 edge[i].flow += Min; 78 edge[i^1].flow -= Min; 79 cost += edge[i].cost * Min; 80 } 81 flow += Min; 82 } 83 } 84 int cnt,s,t; 85 int node[503],val[603]; 86 int st[603],en[603]; 87 void getMap(){ 88 s = ++cnt;t = ++cnt; 89 for(int i = 1;i <= n * 2 + 2;i++){ 90 node[i] = ++cnt; 91 }for(int i = 1;i <= 3 * n;i++)scanf("%d",&val[i]); 92 AddEdge(s,node[1],k,0); 93 AddEdge(node[n * 2 + 2],t,k,0); 94 for(int i = 1;i <= n;i++)st[i] = node[1]; 95 for(int i = n + 1;i <= 3 * n;i++)st[i] = node[i - n + 1]; 96 for(int i = 1;i <= 2 * n;i++)en[i] = node[i + 1]; 97 for(int i = 2 * n + 1;i <= 3 * n;i++)en[i] = node[n * 2 + 2]; 98 for(int i = 1;i <= 3 * n;i++)AddEdge(st[i],en[i],1,-val[i]); 99 for(int i = 1;i <= 2 * n + 1;i++)AddEdge(node[i],node[i + 1],k,0);100 }101 int main()102 {103 scanf("%d %d",&n,&k);104 init();105 getMap();106 int cost, flow;107 MCMF(s,t, cost, flow);108 printf("%d\n",-cost);109 return 0;110 }