题解 P4968 【逃生之路】

· · 题解

题目地址

题目描述：

还是这群生物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之后，拿了54pts。为什么呢？这个效率明明对的呀？出现的问题在于，题目没有说这个价值一定大于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();
}

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

谢谢大家！