题解：P16169 [ICPC 2015 NAIPC] Sand Art

· · 题解

题意简述

将若干颜色的沙子分配到不同隔间。每种颜色在每个隔间内都有体积上下界，每种颜色的总用量不能超过给定值。求所有隔间中最高沙面与最低沙面的最小高度差。

解题思路

设第 i 个隔间的宽度为 d_i，颜色 j 在其中的体积上下界为 l_{i,j},u_{i,j}。先放入所有必须使用的沙子，并定义：

\begin{aligned} b_i & =\sum_j l_{i,j} \\ c_j & =v_j-\sum_i l_{i,j} \\ p_{i,j} & =u_{i,j}-l_{i,j} \end{aligned}

其中，b_i 是隔间 i 的初始体积，c_j 是颜色 j 的剩余供应量，p_{i,j} 是对应位置还能加入的体积。

初始高度的最大值为：

T=\max_i\frac{b_i}{d_i}

最优方案一定可以令最终最大高度恰为 T。任何方案的最大高度都不小于 T，因为下界体积不能删去。

若某个方案的最大高度为 M>T，记隔间 i 的当前高度和初始高度分别为 x_i,a_i。删去额外沙子后，令新高度为：

y_i=\max(a_i,x_i-(M-T))

所有约束只给出额外用量的上界，因此这种删除始终合法。取到高度 M 的隔间会变为 T，其余隔间也不会超过 T。同时有：

\min_i y_i\geq\min_i x_i-(M-T)

故新高度差不超过 T-(\min_i x_i-(M-T))=M-\min_i x_i，不会比原方案更差。

于是只需在不超过 T 的前提下，最大化最终最小高度 H。

固定 H。隔间 i 至少还需要的体积为：

r_i(H)=\max(0,d_iH-b_i)

建立网络流。源点向每种颜色 j 连容量为 c_j 的边，颜色 j 向隔间 i 连容量为 p_{i,j} 的边，隔间 i 向汇点连容量为 r_i(H) 的边。

若最大流等于：

\sum_i r_i(H)

则所有隔间的需求边都被流满。流量直接给出各颜色的额外分配方案，因此最小高度至少为 H。

反过来，任意满足最小高度 H 的分配，在隔间 i 中加入的额外体积至少为 r_i(H)。从该隔间的各颜色额外用量中删去一部分，使总量恰为 r_i(H)。删除不会破坏任何供应量或容量上界，剩余用量便构成一条流满所有需求边的合法流。故该流量条件也是必要的。

可行性关于 H 单调。二分最大的可行 H，答案就是 T-H。

为避免浮点网络流，读取时将所有长度和体积乘以 10^3，转为精确整数。再把二分高度表示成：

H=\frac{q}{10^{18}}

将网络中所有容量同时乘以 10^{18}。此时三类容量分别为：

\begin{aligned} C_{s,j} & =c_j\cdot10^{18} \\ C_{j,i} & =p_{i,j}\cdot10^{18} \\ C_{i,t} & =\max(0,qd_i-b_i\cdot10^{18}) \end{aligned}

它们都是整数，Dinic 的可行性判断没有舍入误差。输入上界下，单条容量不超过 2.5\times10^{28}，全部颜色的容量之和不超过 5\times10^{30}，均在 __int128_t 范围内。

下面证明该精度足以保证三位舍入。

由最大流最小割定理，在需求函数的每一段上，可行性等价于有限个不等式。

这些不等式均形如 DH\leq K。

其中 K 为整数，D 是若干隔间宽度之和。

因此最优 H 的分母不超过 w\cdot10^3\leq5\times10^6。T 的分母也满足该上界，所以真实答案 A=T-H 的分母不超过 2.5\times10^{13}。

任意不相等的 A 与三位小数舍入分界 \frac{2k+1}{2000} 之间，距离至少为：

\frac{1}{2.5\times10^{13}\cdot2000}=2\times10^{-17}

二分从答案偏大的一侧逼近，误差小于 10^{-18}。

因此不会跨过任何不相等的舍入分界。

若答案恰在分界上，偏大的一侧会按要求向上舍入。

记二分得到的近似答案为 A_q。

代码再用整数运算计算：

R=\left\lfloor1000A_q+\frac{1}{2}\right\rfloor

最后只将已经舍入的 R/1000 交给 setprecision(3) 输出。

设 V=n+m+2，E=nm+n+m。每次判定在该网络上运行 Dinic。按通用上界，总时间复杂度为 O(V^2E\log(h\cdot10^{18}))，空间复杂度为 O(E)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using i128=__int128_t;
const int N=205;
const int V=405;
const ll mul=1000;
const i128 prc=(i128)1000000000000000000LL;
const i128 inf=(i128)1<<120;
struct Edge
{
    int v;
    size_t id;
    i128 cap;
};
vector<Edge> G[V];
ll b[N],c[N],d[N],mn[N][N],p[N][N];
int dep[V];
size_t cur[V];
int n,m,s,t;
ll read()
{
    string str;
    cin>>str;
    size_t pos=str.find('.');
    if(pos==string::npos)return stoll(str)*mul;
    string dec=str.substr(pos+1);
    while(dec.size()<3)dec.push_back('0');
    return stoll(str.substr(0,pos))*mul+stoll(dec);
}
void add(int u,int v,i128 cap)
{
    size_t uid=G[u].size(),vid=G[v].size();
    G[u].push_back({v,vid,cap});
    G[v].push_back({u,uid,0});
}
bool bfs()
{
    fill(dep,dep+t+1,-1);
    queue<int> q;
    dep[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(const Edge &e:G[u])
        {
            if(e.cap==0||dep[e.v]!=-1)continue;
            dep[e.v]=dep[u]+1;
            q.push(e.v);
        }
    }
    return dep[t]!=-1;
}
i128 dfs(int u,i128 f)
{
    if(u==t)return f;
    for(size_t &i=cur[u];i<G[u].size();i++)
    {
        Edge &e=G[u][i];
        if(e.cap==0||dep[e.v]!=dep[u]+1)continue;
        i128 res=dfs(e.v,min(f,e.cap));
        if(res==0)continue;
        e.cap-=res;
        G[e.v][e.id].cap+=res;
        return res;
    }
    return 0;
}
bool check(i128 h)
{
    s=0;
    t=m+n+1;
    for(int i=0;i<=t;i++)G[i].clear();
    for(int j=0;j<m;j++)add(s,j+1,(i128)c[j]*prc);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)add(j+1,m+i+1,(i128)p[i][j]*prc);
    }
    i128 sum=0;
    for(int i=0;i<n;i++)
    {
        i128 val=max(h*d[i]-(i128)b[i]*prc,(i128)0);
        add(m+i+1,t,val);
        sum+=val;
    }
    i128 res=0;
    while(bfs())
    {
        fill(cur,cur+t+1,0);
        while(1)
        {
            i128 val=dfs(s,inf);
            if(val==0)break;
            res+=val;
        }
    }
    return res==sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int w,h;
    cin>>n>>m>>w>>h;
    for(int j=0;j<m;j++)c[j]=read();
    ll pre=0;
    for(int i=0;i<n-1;i++)
    {
        ll pos=read();
        d[i]=pos-pre;
        pre=pos;
    }
    d[n-1]=(ll)w*mul-pre;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            mn[i][j]=read();
            c[j]-=mn[i][j];
            b[i]+=mn[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)p[i][j]=read()-mn[i][j];
    }
    int pos=0;
    for(int i=1;i<n;i++)
    {
        if(b[i]*d[pos]>b[pos]*d[i])pos=i;
    }
    i128 l=0,r=min((i128)b[pos]*prc/d[pos],(i128)h*prc)+1;
    while(l<r)
    {
        i128 mid=(l+r)>>1;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    l--;
    i128 num=(i128)b[pos]*prc-l*d[pos],den=(i128)d[pos]*prc;
    ll ans=(ll)((num*2000+den)/(den*2));
    cout<<fixed<<setprecision(3)<<(long double)ans/1000<<'\n';
    return 0;
}