Vijos 学姐的逛街计划

传送门

题解传送门

线性规划，最小费用最大流。

神奇的操作。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<queue>

#include<ctime>

#include<cmath>

#define inf 1e18

const int N=;

typedef long long LL;

using namespace std;

int n,k;

LL c[N];

template<typename T> void read(T &x) {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct edge {

    int u,v,nx;

    LL fl,cap,cost;

    edge(){}

    edge(int u,int v,LL fl,LL cap,LL cost,int nx):u(u),v(v),fl(fl),cap(cap),cost(cost),nx(nx){}

}e[N];

int fir[N],ecnt=;

void add(int u,int v,LL cap,LL cost) {

    e[++ecnt]=edge(u,v,,cap,cost,fir[u]); fir[u]=ecnt;

    e[++ecnt]=edge(v,u,,,-cost,fir[v]); fir[v]=ecnt;

}

int vis[N],p[N];

LL dis[N];

queue<int>que;

int spfa(int s,int t) {

    for(int i=;i<=n;i++) vis[i]=,dis[i]=inf;

    que.push(s); dis[s]=;

    while(!que.empty()) {

        int x=que.front();

        que.pop(); vis[x]=;

        for(int i=fir[x];i;i=e[i].nx)

        if(e[i].cap>e[i].fl) {

            int y=e[i].v;

            if(dis[y]>dis[x]+e[i].cost) {

                dis[y]=dis[x]+e[i].cost;

                p[y]=i;

                if(!vis[y]) {

                    vis[y]=;

                    que.push(y);

                }

            }

        }

    }

    return dis[t]!=inf;

}

LL calc(int s,int t) {

    LL fl=inf,res=;

    for(int i=t;i!=s;i=e[p[i]].u)

        fl=min(fl,e[p[i]].cap-e[p[i]].fl),

        res+=e[p[i]].cost;

    for(int i=t;i!=s;i=e[p[i]].u)

        e[p[i]].fl+=fl,e[p[i]^].fl-=fl;

    return fl*res;

}

LL max_flow(int s,int t) {

    LL res=;

    while(spfa(s,t))

        res+=calc(s,t);

    return res;

}

int main() {

    read(n); read(k);

    for(int i=;i<=*n;i++) read(c[i]);

    int s=*n+,t=s+;

    add(s,*n+,k,);

    add(*n+,t,k,);

    for(int i=;i<=n;i++) {

        add(i,*n+,,-c[i]);

        add(*n+,n+i,,-c[*n+i]);

        add(n+i,i,,-c[n+i]);

    }

    for(int i=;i<=*n;i++) add(i,i-,k,);

    add(,*n+,k,);

    add(*n+,*n,k,);

    n=t;

    LL ans=-max_flow(s,t);

    printf("%lld\n",ans);

    return ;

}