Heidi and Library (hard) | CodeForces 802C最大流最小费用

// LUOGU_RID: 90857083
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
using namespace std;
const int maxn=100010;

bool vis[maxn];
int n,m,k,s,t,x,y,z,f,Pre[maxn],book[maxn],a[maxn],c[maxn],dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量 
struct Edge{
    int to,next,flow,dis;//flow流量 dis花费 
}edge[maxn];
int head[maxn],num_edge; 
queue <int> q;


void add_edge(int from,int to,int flow,int dis)
{
    edge[++num_edge].next=head[from];edge[num_edge].to=to;edge[num_edge].flow=flow;edge[num_edge].dis=dis;head[from]=num_edge;
    // 反向边流量为0，费用为负数
    edge[++num_edge].next=head[to];edge[num_edge].to=from;edge[num_edge].flow=0;edge[num_edge].dis=-dis;head[to]=num_edge;
}

bool spfa(int s,int t)
{
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
    
    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for (int i=head[now]; i!=-1; i=edge[i].next)
        {
            if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边 
            {
                dis[edge[i].to]=dis[now]+edge[i].dis;
                pre[edge[i].to]=now;
                last[edge[i].to]=i;
                flow[edge[i].to]=min(flow[now],edge[i].flow);//
                if (!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    q.push(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}

void MCMF()
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {//从源点一直回溯到汇点 
            edge[last[now]].flow-=flow[t];//flow和dis容易搞混 
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}

int main()
{
    //freopen("lys.in","r",stdin);
    memset(head,-1,sizeof(head)); num_edge=-1;//初始化 
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    
    s=0;t=2*n+1;
    for(int i=1;i<=n;i++){
        /*
         拆点，对每一天拆成in 和 out
         流量为1,费用为c[i]表示当天的书必买 
         这样就能起码保证一种方案，就是说最大流就可以保证了。
         因为要决策每一天买不买不好表示，emmm也不是不行但可能
         需要用很复杂的状态表示，活生生做成dp&flow是吧
         考虑补集最近真的见到很多次了，我也该记住了，哪怕再笨
         考虑先把所有都买了——然后考虑是否有方案能够减少花费 
        */
        add_edge(s,i,1,c[a[i]]);
        /*
        in -> out,表示当天就把这本书丢了or卖了 
        */
        add_edge(i,i+n,1,0);// 流量限制为1表示丢了or卖了,only one choice 
        add_edge(i+n,t,1,0);//丢了 
        /*
          表示当天买的这本书在下一次需要的前一天给卖了，
          这样第二天买入的时候等价于-c+c,mean while we save us; 
        */
        if(Pre[a[i]]) add_edge(i-1,Pre[a[i]]+n,1,-c[a[i]]);
        Pre[a[i]]=i;
        // 这玩意要边走边维护，刚才煞笔了唔 
        /*
         为了限制流量,当天流向下一天的为k-1本，还有一个位置留给第二天强制买
         咋保留？就上面辣个先卖了，再买， 
        */
        if(i!=n) add_edge(i,i+1,k-1,0);
    }
    MCMF();
    cout<<mincost;
    return 0;
}