自动搬运

查看原文

来自洛谷，原作者为

	阿廖 **

搬运于2025-08-24 22:05:45，当前版本为作者最后更新于2018-11-04 14:44:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目地址

题目描述：

还是这群生物ccj，因为上次的打击太草率了，同时被他人侦测到了。在得知自己即将受到黑暗森林打击之后，选择逃离自己的家园。

他们的旅程计划在一条线上，其中，我们约定，一号点是他们的家园，有无限多个生物。每一个星球，都可以向之后连续的$p$个星球进行转移。但由于每个星球的”体质“不同，每个星球所能接受的生物数量限定在一个范围$[b,a]$之间。而且，由于星球本身资源匮乏，到达每一个星球都需要消耗星球一定的能源，补充飞船能源。并且又因为宇宙空间的复杂，所以这个能源是关于星球所接受生物数量的一个多项式。飞船年久失修，所以遇到任何星球必定前往去补充能源。

可惜这群生物有一个睿智的头领，他希望最终能有生物到达可以生存的星球，而且消耗的总能源要尽量少。那群生物对这个头领很失望，于是把任务丢给你。

请求出有生物到达可生存星球的情况下，最少的能源消耗是多少？

数据范围：

$2<=n<=100\quad |w|<=100\quad 1<=b<=a<=100\quad 1<=k<=5\quad 0<=p<=10$

保证多项式函数二阶导函数在$x∈[1,100]$时恒大于$0$

详细范围参见“标程”

题解部分：

这题显然是一种方案最优化问题，对于方案最优化问题，目前我已知的效率和正确性稳定的算法有以下四大类：暴力，贪心，动态规划，网络流。而这道题目，贪心显然不可以，所以只剩下三种方法，分别讨论。

暴力emmmmmmm，pass！

动态规划，对于这种方案型，一定要有至少$1$维存当前方案和转移方案，而这个可以从之前$p$个星球转移过来，所以目测$p$维数组，空间一定应该开不下，pass！

只剩下孤苦伶仃的网络流了……所以std的算法也非常显然了。首先我们看到，对于不同的生物转移数量，有不同的能源消耗，这显然就是费用流的常规套路嘛……然后，生物可以按一定顺序后向移动，这显然就是网络流嘛……但是题目说到，这个生物有到达就可以，意味着不用求取最大流。好的，现在问题转化成，最小费用可行流怎么建图。

我们发现有两个难点，一是费用不是正比例函数，二是生物数量有上下界限制。网络流的效率要保证，中间一定不能有多余的计算，否则理论效率的费用流$n^2m^2$跑起来会很感人。我们注意到一个条件，多项式的二阶导函数恒大于$0$，而系数都是整数，这意味着对于整点的一阶差分序列，一定是单调递增的。在观看蓝书之后**我们考虑最小费用流的一个性质，对于最小费用流，在有重边的情况下，会选择最小价值的一条边跑。**一阶差分序列又有一个特性，$f(i)=\sum_{j=1}^i f^{'}(j)$这样一来，我们将单位流量1建边，每次通过最小费用流的“前缀和”计算，得到相应的$f(i)$，就解决的这个难点。一个小优化，对于每个单位的计算，我们可以拆点，将点的计算限制放到边上，也就是出现了$10000$条边。

对于第二个难点，我们可以直接采用带上下界的可行流的方式建图，因为费用流本身建立于可行流之上，只要可行流求出来，费用就算遍历一遍也能求出来，当然，还要保证最小。那这种图怎么建呢？我们考虑可行流的一个性质，除了源点和汇点，保证每个点流量平衡。假设从$i$到$j$至少流$b$的流量，最多流$a$的流量。直观上看，如果有解，只有$b$~$a$的那段会出现变动，流量小于$b$的部分一定要流过去，所以从$i$到$j$建立$a-b$容量的边。这样一来，$i$少出去$b$的流量，$j$少得到$b$的流量，怎么办呢？建立附加点$ex1$和$ex2$，从$i$向$ex1$连流量$b$的边，从$ex2$向$j$连流量$b$的边，保证这两个点流量平衡。这时候，我们把原图中的汇点向源点连接$INF$的边，表示从源点最多向汇点跑$INF$的流量，这条边为了保证源点和汇点的流量平衡。等这些边建立完毕，从$ex2$向$ex1$跑一遍最大流。为什么呢？跑完最大流后，如果满流，说明有解，因为$ex2$连出去都都是各个边的$b$，也就是下限。下限被满足，意味着有解了。这时候，我们忽略这两个附加点，从源点向汇点再跑一次最小费用可行流，就可以得到答案了。**注意，这几次跑网络流答案不能清空，因为都是对于同一个图进行多次往返，计算合理的答案。**这个图中，把原先的每条边拆成$3$条，点数增加$2$个。一共边$13000$，点$100$根据LG的最小费用最大流模板题这个效率太快了，显然可以过去。

想到这里，你是否会觉得万事大吉了？如果你花了好大心血，写完这些，会发现$TLE$之后，拿了$54$pts。为什么呢？这个效率明明对的呀？出现的问题在于，题目没有说这个价值一定大于$0$啊！最小费用流本身使用最短路算法求解，如果一旦出现负环，就无法得到解了。但是常识告诉我们，网络流中有上限，就算有负环，还是可以解出，只不过在那个负环中我们跑满流，保证答案最优，所以想办法解决问题。这个被解决的图，也就是刚刚建的图，换句话说，我们需要二次构图！

再次搜刮脑中关于网络流的知识，我们又会发现，曾经好像网络流会被用作求解欧拉回路！**在求解欧拉回路时，我们通过转化，把每个点的入度等于出度转化成流量平衡。**所以我们需要再次利用以下这个性质，把图中每个点拆成两个点，建立另外的源点和汇点。从源点向每个点连一条$INF$，把每个点和它的分身连一条$INF$，把每个分身向汇点连一条$INF$。这时候，图中的最大流显然是$INF$，也就是说每个点都构成一个从源点到汇点的通路。因为是最小费用流，我们把原来的$i$到$j$的边，变成$i$到$j$的分身。首先，这个图，不存在环。之后，我们来证明这个图能求解负环。如果原图存在负环，那么一定会用循环流，这个循环流在新图怎么表示呢？显然就是一个点集，他们之间会互相向其他某些点的分身连边，自己同样也会收到边。如果是循环流，意味着每个点的入度还是等于出度。因为原图已经是最大流，所以求解时为了继续保证最大流，一定从分身出去的点都是$INF$，中间的流量转移必须相等，才能保证每个点在中间转移之后出去依然是$INF$。又由于是费用流，所以一定会选择费用最小的边去跑最大流。在负环的情况下，它就会用负环中最小容量的边去填充负环，因为流量要是大于最小容量，这个边就无法通过，负环不复存在。在这个新图中，这支循环流，就会在中间的点中流来流去，**但是因为循环流，所以一定还会流回原来的点，即满足出去后到达汇点的流量是$INF$，满足最大流这个性质，但这些边的值已经被改变，新图虽然最大流一直是$INF$，价值却不一样。通过这次操作，我们就知道哪些边会被跑满，再次提取出来重建原图时，原图就不存在负环，且已经有价值，但没有流量，因为循环流保证之间的流量平衡，没有流到汇点。**通过这样的二次构图，我们就可以消去负环，愉快跑网络流。对于这个新图，边是之前的$3$倍，点是之前的$2$倍加$2$，也就是$40000$的边，$200$的点。还是根据LG的模板题数据范围这样的效率我们能够接受，所以就能愉快AC啦！

提醒一下，这题的多项式会爆$int$，需要用$ll$存储结果。

由于这题建边复杂，在此提供std部分代码。

建边部分保证能看懂，add(u,v,cap,val)，其他部分拒绝解释，请自行完成代码！

inline long long pre()
{
    register int N=2*n+4,exs=2*N+1,ext=2*N+2;
    flow.init(2*N+2);
    flow.add(t,s+N,INF,0),flow.add(s,1+N,INF,0),m=5;
    for(register int i=2;i<=n;++i)
        if(f[i])flow.add(i+n,t+N,INF,0),m+=2;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=jump;++j)
        {
            if(i+j>n)break;
            if(i!=1)flow.add(i+n,i+j+N,INF,0),m+=2;
            else flow.add(i,i+j+N,INF,0),m+=2;
        }
    for(register int i=2;i<=n;++i)
    {
        for(register int j=1;j<=a[i];++j)
            if(j<=b[i])
                flow.add(i,ex1+N,1,chafen[j][i]),m+=2;
            else
                flow.add(i,i+n+N,1,chafen[j][i]),m+=2;
        flow.add(ex2,i+n+N,b[i],0),m+=2;
    }
    for(register int i=1;i<=2*n+4;++i)
    	flow.add(exs,i,INF,0),flow.add(i,i+N,INF,0),flow.add(i+N,ext,INF,0);
    flow.work(exs,ext,1);
    for(register int i=2;i<=m;++i,++i)
            edge[i].start=flow.extract_edge(i,1),edge[i].end=flow.extract_edge(i,2)-N,edge[i].val=flow.extract_edge(i,3),edge[i].cost=flow.extract_edge(i,4);
    for(register int i=3;i<=m;++i,++i)
            edge[i].start=flow.extract_edge(i,1)-N,edge[i].end=flow.extract_edge(i,2),edge[i].val=flow.extract_edge(i,3),edge[i].cost=flow.extract_edge(i,4);
    return flow.mn_cost();
}
inline long long make()
{
    long long ans=pre();
    flow.init(2*n+4);
    for(register int i=2;i<=m;++i)
    	flow.force_add(edge[i].start,edge[i].end,edge[i].val,edge[i].cost);
    flow.work(ex2,ex1,1);
    if(tot_b!=flow.mx_flow())return INF;
    flow.work(s,t,0);
    return ans+flow.mn_cost();
}

本题预计难度：~~黑？~~紫题。

谢谢大家！