学姐的逛街计划
描述
doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.
偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.
doc 很忧伤, 因为他还要陪学姐去逛街呢.
后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.
现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商.
doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.
可是, 究竟这个和最大能是多少呢?
格式
输入格式
第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.
第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数
输出格式
输出只有一个整数, 表示可以取到的最大智商和.
样例1
样例输入1
样例输出1
限制
对于 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代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4;
const int M = 4e5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct Edge
{
int from, to, cap, flow, cost, next;
};
Edge edge[M];
int head[N], inde,pre[N], dist[N];
bool vis[N];
int n,k;
void init()
{
inde = ;
memset(head, -, sizeof(head));
}
void AddEdge(int u, int v, int w, int c)
{
Edge E1 = {u, v, w, , c, head[u]};
edge[inde] = E1;
head[u] = inde++;
Edge E2 = {v, u, , , -c, head[v]};
edge[inde] = E2;
head[v] = inde++;
}
bool SPFA(int s, int t)
{
queue<int> Q;
memset(dist, INF, sizeof(dist));
memset(vis, false, sizeof(vis));
memset(pre, -, sizeof(pre));
dist[s] = ;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = false;
for(int i = head[u]; i != -; i = edge[i].next)
{
Edge E = edge[i];
if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow)
{
dist[E.to] = dist[u] + E.cost;
pre[E.to] = i;
if(!vis[E.to])
{
vis[E.to] = true;
Q.push(E.to);
}
}
}
}
return pre[t] != -;
}
void MCMF(int s, int t, int &cost, int &flow)
{
flow = ;
cost = ;
while(SPFA(s, t))
{
int Min = INF;
for(int i = pre[t]; i != -; i = pre[edge[i^].to])
{
Edge E = edge[i];
Min = min(Min, E.cap - E.flow);
}
for(int i = pre[t]; i != -; i = pre[edge[i^].to])
{
edge[i].flow += Min;
edge[i^].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
}
int cnt,s,t;
int node[],val[];
int st[],en[];
void getMap(){
s = ++cnt;t = ++cnt;
for(int i = ;i <= n * + ;i++){
node[i] = ++cnt;
}for(int i = ;i <= * n;i++)scanf("%d",&val[i]);
AddEdge(s,node[],k,);
AddEdge(node[n * + ],t,k,);
for(int i = ;i <= n;i++)st[i] = node[];
for(int i = n + ;i <= * n;i++)st[i] = node[i - n + ];
for(int i = ;i <= * n;i++)en[i] = node[i + ];
for(int i = * n + ;i <= * n;i++)en[i] = node[n * + ];
for(int i = ;i <= * n;i++)AddEdge(st[i],en[i],,-val[i]);
for(int i = ;i <= * n + ;i++)AddEdge(node[i],node[i + ],k,);
}
int main()
{
scanf("%d %d",&n,&k);
init();
getMap();
int cost, flow;
MCMF(s,t, cost, flow);
printf("%d\n",-cost);
return ;
}