vijos1891 学姐的逛街计划（线性规划）

P1891学姐的逛街计划

描述

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.

【思路】

　　一道线性规划的题目，好神奇=-=。

　　这是题解中的思路：

【代码】

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long LL ;

 const int maxn = +;

 const int INF = 1e9;

 struct Edge{ int u,v,cap,flow,cost;

 };

 struct MCMF {

     int n,m,s,t;

     int inq[maxn],a[maxn],d[maxn],p[maxn];

     vector<int> G[maxn];

     vector<Edge> es;

     void init(int n) {

         this->n=n;

         es.clear();

         for(int i=;i<n;i++) G[i].clear();

     }

     void AddEdge(int u,int v,int cap,int cost) {

         es.push_back((Edge){u,v,cap,,cost});

         es.push_back((Edge){v,u,,,-cost});

         m=es.size();

         G[u].push_back(m-);

         G[v].push_back(m-);

     }

     bool SPFA(int s,int t,int& flow,LL& cost) {

         for(int i=;i<n;i++) d[i]=INF;

         memset(inq,,sizeof(inq));

         d[s]=; inq[s]=; p[s]=; a[s]=INF;

         queue<int> q; q.push(s);

         while(!q.empty()) {

             int u=q.front(); q.pop(); inq[u]=;

             for(int i=;i<G[u].size();i++) {

                 Edge& e=es[G[u][i]];

                 int v=e.v;

                 if(e.cap>e.flow && d[v]>d[u]+e.cost) {

                     d[v]=d[u]+e.cost;

                     p[v]=G[u][i];

                     a[v]=min(a[u],e.cap-e.flow);        //min(a[u],..)

                     if(!inq[v]) { inq[v]=; q.push(v);

                     }

                 }

             }

         }

         if(d[t]==INF) return false;

         flow+=a[t] , cost+=a[t]*d[t];

         for(int x=t; x!=s; x=es[p[x]].u) {

             es[p[x]].flow+=a[t]; es[p[x]^].flow-=a[t];

         }

         return true;

     }

     int Mincost(int s,int t,LL& cost) {

         int flow=; cost=;

         while(SPFA(s,t,flow,cost)) ;

         return flow;

     }

 } mc;

 int n,m,k;

 int a[maxn];

 int main() {

     scanf("%d%d",&n,&k);

     FOR(i,,*n) scanf("%d",&a[i]);

     mc.init(*n+);

     int s=,t=*n+;

     FOR(i,,n+) mc.AddEdge(s,i,,-a[i-]);

     FOR(i,n+,*n+) mc.AddEdge(i-n,i,,-a[i-]);

     FOR(i,n+,*n+) mc.AddEdge(i,*n+,,-a[i-+n]);

     FOR(i,,*n+) mc.AddEdge(i-,i,k,);

     mc.AddEdge(s,,k,);

     mc.AddEdge(*n+,t,k,);

     LL cost;

     mc.Mincost(s,t,cost);

     printf("%lld",-cost);

     return ;

 }

逛街