题解：P7233 [JSOI2014] 电信网络

· · 题解

题意

给出 n 个基站，第 i 个基站可以选择升级为 3G 基站并获得 s_i 的价值，但是需要满足它所在通信范围内所有基站都升级为 3G 基站。

解析

看到这种有前置的选择问题时，我们不难想到使用网络流进行求解。我们将基站放入集合 S 视为升级，放入集合 T 视为不升级，这就转换成了一个经典的最小割问题模型。如果 s_i > 0，就连接一条 s 到 i 的边权为 s_i 的边，否则连接一条 i 到 t 的边权为 -s_i 的边。如果选择了节点 u 就必须选节点 v，就连接一条 u 到 v 的边权为 \infty 的边进行限制。最后，所有正的 s_i 的和减去最小割即为题目所求的答案。

AC 代码

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

// 本人习惯 HLPP，不像看的可以跳过
template<typename T>
struct HLPP
{
    struct edge
    {
        int v,rev; T w;
        edge()=default;
        edge(int v,int rev,const T& w)
            :v(v),rev(rev),w(w){}
    };

    int n,s,t,maxh;
    vector<vector<edge>> gra;
    vector<int> h;
    vector<int> cnt;
    vector<T> exf;
    vector<bool> inb;
    vector<vector<int>> b;

    HLPP(int n):n(n),maxh(0),gra(n),
                h(n),cnt(n),exf(n),
                inb(n),b(n<<1|1){}

    void adde(int u,int v,const T& w,const T& rw=0)
    {
        gra[u].emplace_back(v,gra[v].size(),w);
        gra[v].emplace_back(u,gra[u].size()-1,rw);
    }

    void addb(int u)
    {
        if(inb[u]) return;
        if(u==s||u==t) return;

        inb[u]=true;
        b[h[u]].emplace_back(u);
        if(h[u]>maxh) maxh=h[u];
    }

    bool bfs()
    {
        fill(h.begin(),h.end(),n<<1);
        h[t]=0;
        queue<int> q;
        q.emplace(t);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(auto& [v,rev,w]:gra[u])
            {
                if(gra[v][rev].w==0) continue;
                if(h[v]!=n<<1) continue;

                h[v]=h[u]+1;
                q.emplace(v);
            }
        }

        if(h[s]==n<<1) return true;

        h[s]=n;
        for(int i=0;i<n;++i)
        {
            if(h[i]<n)
            {
                ++cnt[h[i]];
            }
        }
        return false;
    }

    void relabel(int u)
    {
        if(h[u]<n&&!--cnt[h[u]])
        {
            for(int i=0;i<n;++i)
            {
                if(h[u]<=h[i]&&h[i]<n)
                {
                    h[i]=n+1;
                }
            }
            return;
        }

        h[u]=n<<1;
        for(auto& [v,rev,w]:gra[u])
        {
            if(w==0) continue;
            if(h[v]<h[u]) h[u]=h[v];
        }
        ++h[u];
        if(h[u]<n)
        {
            ++cnt[h[u]];
        }
    }

    void push(int u)
    {
        while(exf[u]!=0)
        {
            for(auto& [v,rev,w]:gra[u])
            {
                if(w==0) continue;
                if(h[u]!=h[v]+1) continue;

                T flow=min(w,exf[u]);
                w-=flow;
                gra[v][rev].w+=flow;
                exf[u]-=flow;
                exf[v]+=flow;
                addb(v);
                if(exf[u]==0) return;
            }
            relabel(u);
        }
    }

    int getu()
    {
        while(maxh>=0&&b[maxh].empty()) --maxh;
        if(maxh<0) return -1;
        int u=b[maxh].back();
        b[maxh].pop_back();
        inb[u]=false;
        return u;
    }

    T maxf(int s_,int t_)
    {
        s=s_,t=t_;

        if(bfs()) return 0;

        for(auto& [v,rev,w]:gra[s])
        {
            if(w==0) continue;

            T flow=w;
            w-=flow;
            gra[v][rev].w+=flow;
            exf[s]-=flow;
            exf[v]+=flow;
            addb(v);
        }

        int u;
        while(~(u=getu()))
        {
            push(u);
        }

        return exf[t];
    }
};

// 判断一个节点是否能到另一个节点的辅助函数
bool to(const pair<int,int>& a,const pair<int,int>& b,int d)
{
    int dx=a.first-b.first;
    int dy=a.second-b.second;
    return dx*dx+dy*dy<=d*d;
}

constexpr int INF=0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    int s=n;
    int t=n+1;
    HLPP<int> gra(t+1);
    int tot=0;

    vector<pair<pair<int,int>,int>> jz(n);
    for(int i=0;i<n;++i)
    {
        auto& [zb,d]=jz[i];
        int ss=0;
        cin>>zb.first>>zb.second>>d>>ss;

        if(ss>0)
        {
            tot+=ss;
            gra.adde(s,i,ss);
        }
        else
        {
            gra.adde(i,t,-ss);
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i==j) continue;

            if(to(jz[i].first,jz[j].first,jz[i].second))
            {
                gra.adde(i,j,INF);
            }
        }
    }
    cout<<tot-gra.maxf(s,t);
}