题解：P15011 [UOI 2019 II Stage] 土豆

· · 题解

源点向每个城市连 p_i 的边，每个掩体向汇点连 c_i 的边。然后二分答案 t，对于每个城市 x 和掩体 y 若 \operatorname{dist}(x,y) \le t 则 x 向 y 连容量 +\infty 的边，这个问题变成求这个二分图有没有完美匹配。

直接网络流应该是跑不过的，考虑 HALL 定理：

假设 G=(X,Y,E) 是二分图，且 |X|\le|Y|。对于任何 W\subseteq X，记 NG(W) 为图 G 中所有与 W 中的顶点相邻的顶点集合。那么，X 完美匹配存在，当且仅当 |W|\le NG(|W|) 对于所有 W\subseteq X 都成立。

那二分 t，算出对于每个左部点能到达的右部点的集合 M_i，然后求出 f_M=\sum_{M_i \subseteq M} p_i ，g_M=\sum_{i\in M}c_i，对于所有 M，若都有 |f_M|\leq|g_M| 则能够在 t 时间内完成运输，否则不行。注意到掩体个数 s 很小，可以用 SOSDP 计算。

constexpr int N=100010,K=20,P=262154;
int a[N],pos[K],cap[K],mask[N];
ll dis[K][N];
ll l[P],r[P];
int main(int argc,char** argv)
{
    if(argc==3)freopen(argv[1],"r",stdin),freopen(argv[2],"w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[y].push_back({x,z});
    }
    for(int i=1;i<=k;i++)cin>>pos[i]>>cap[i];
    auto dijkstra=[&](int s,ll* dis)
    {
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
        fill(dis+1,dis+n+1,inf<ll>);
        vector<char>vis(n+1,0);
        dis[s]=0;
        pq.push({dis[s],s});
        while(!pq.empty())
        {
            auto[d,x]=pq.top();
            pq.pop();
            if(vis[x])continue;
            vis[x]=1;
            for(auto[y,w]:g[x])
            if(dis[y]>dis[x]+w)
            pq.push({dis[y]=dis[x]+w,y});
        }
    };
    for(int i=1;i<=k;i++)dijkstra(pos[i],dis[i]);
    auto sosdp=[&](int n,ll* f)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<1<<n;j++)
                if(j>>i&1)
                    f[j]+=f[j^1<<i];
    };
    for(int mask=0;mask<1<<k;mask++)
        for(int i=1;i<=k;i++)
            if(mask>>(i-1)&1)
                r[mask]+=cap[i];
    auto check=[&](ll t)
    {
        fill(l,l+(1<<k),0);
        for(int i=1;i<=n;i++)
        {
            int mask=0;
            for(int j=1;j<=k;j++)
            if(dis[j][i]<=t)
            mask|=1<<(j-1);
            l[mask]+=a[i];
        }
        sosdp(k,l);
        for(int mask=0;mask<1<<k;mask++)if(l[mask]>r[mask])return false;
        return true;
    };
    ll l=0,r=inf<ll>-10,ans=-1;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}