题解：P7233 [JSOI2014] 电信网络

· · 题解

随机跳题跳到了这一题，发现一个 10 年前的省选题居然没有题解，从来没有写过题解的我就来写一篇吧。

题目描述

对于在 i 塔通信范围内的塔 j 建立有向边 (i,j)，题目意思可概括为：有 500 个点的有向图，每个点有可正可负的权值，要求选取一些点使其权值之和最大，但要求每个被选取的点的后继结点也必须被选取。

方法一

由于本人灵光不足，没有想到转化为网络流的做法，所以只能暴力搜索。

朴素做法

采取搜索回溯，先尝试选取点 1，并选取其所有后继结点，完成后将当前权值和与搜索到的最大权值 (ans) 比较，然后进入下一层递归，从 2 号结点继续往后搜索，递归函数返回后，尝试选取点 2，以此继续。代码：

void doit(int x)
{
    int que[520];
    for(int i=x;i<=n;i++)
    {
        if(vis[i])continue;
        vis[i]=1;
        tans+=w[i]; 
        int tot=1;
        que[1]=i;
        for(int j=1;j<=tot;j++)
        {
            int now=que[j];
            for(int k=1;k<=iq[now];k++)//iq[now]是now结点的后继数量
            {
                if(!vis[imap[now][k]])//采用邻接表存图
                {
                    que[++tot]=imap[now][k];
                    tans+=w[que[tot]];
                    vis[que[tot]]=1;
                }
            }
        }
        ans=max(ans,tans);
        doit(i+1);
        for(int j=1;j<=tot;j++)
        {
            tans-=w[que[j]];
            vis[que[j]]=0;
        }
    }
}

这样暴力的搜索居然可以得到 60 分！这就意味着可以抄别人的代码了

一级优化

朴素做法超时 4 个点。

稍稍思考就可以发现，对于权值 <0 的点，我们完全没有必要主动选取，我们只有可能因为其前驱正权结点被选取而不得不选取它，所以稍作修改，只尝试选取正权结点：

void doit(int x)
{
    int que[520];
    for(int i=x;i<=q;i++)//q存储正权结点总数
    {
        if(vis[a[i]])continue;//a数组存储正权结点编号
        vis[a[i]]=1;
        tans+=w[a[i]]; 
        int tot=1;
        que[1]=a[i];
        for(int j=1;j<=tot;j++)
        {
            int now=que[j];
            for(int k=1;k<=iq[now];k++)
            {
                if(!vis[imap[now][k]])
                {
                    que[++tot]=imap[now][k];
                    tans+=w[que[tot]];
                    vis[que[tot]]=1;
                }
            }
        }
        ans=max(ans,tans);
        doit(i+1);
        for(int j=1;j<=tot;j++)
        {
            tans-=w[que[j]];
            vis[que[j]]=0;
        }
    }
}

这样就可以得到 90 分了，但依然不能通过……

二级优化

继续想办法优化。

注意到，如果选取某个正权结点时没有引起必须选取一些负权结点，那么这样的选取肯定是纯粹有益的，这样的更改没有必要撤销，因此在搜索时可以不用递归进入下一层。这样优化之后，就可以通过了~

根据作者提交情况，单个测试点最长用时 64ms，开 O2 的话是 40ms 左右。

通过代码

#include<bits/stdc++.h>//2024-3-13第一版，90pts；3-15最终版本 
using namespace std;
int x[550],y[550],r[550],w[550],n,a[550],q;
int imap[550][550],iq[550];
bool vis[550];
int ans=0,tans;
void doit(int x)
{
    int que[5200];  
    int tot=1;
    for(int i=x;i<=q;i++)
    {
        if(vis[a[i]])continue;
        bool ok=1;
        int tott=tot;
        vis[a[i]]=1;
        tans+=w[a[i]]; 

        que[1]=a[i];
        for(int j=1;j<=tot;j++)
        {
            int now=que[j];
            for(int k=1;k<=iq[now];k++)
            {
                if(!vis[imap[now][k]])
                {
                    que[++tot]=imap[now][k];
                    tans+=w[que[tot]];
                    if(w[que[tot]]<0)ok=0;
                    vis[que[tot]]=1;
                }
            }
        }
        ans=max(ans,tans);
        if(ok)continue;
        doit(i+1);
        for(int j=tott;j<=tot;j++)
        {
            tans-=w[que[j]];
            vis[que[j]]=0;
        }
        tot=tott;
    }
    if(tot>1)
    {
        for(int j=1;j<=tot;j++)
        {
            tans-=w[que[j]];
            vis[que[j]]=0;
        }
    }
}
int main()
{
    cin>>n; 
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>r[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i])<=r[i]*r[i])
            {
                imap[i][++iq[i]]=j;
            }
        }
        if(w[i]>0)a[++q]=i;
    }
    doit(1);
    cout<<ans;
return 0;
}

方法二

通过后，看了看其他人的满分代码，看到函数名 dinic，心情复杂……我第一感觉也是网络流啊，但是没想出来具体的做法啊……

以下是读完代码后我自己的理解。

首先令正权点已经全部选取，负权点都没有选取。 构建源点指向正权点的边权为正权点权值的有向边，然后再构建负权点指向汇点的边权为负权点权值的绝对值的有向边，对于原图中有向边(就是文章开头说的那个)，把它的权值设为无穷大。

现在，如果由源点到汇点有路径，那么说明存在不符合题目要求的情况。为了使得方案符合题目要求，可以进行如下操作：

1.对于负权点 i，消耗 abs(weight[i]) 的收益，选取 i 点，相当于割断 i 到汇点的边；

2.对于正权点 j，减少 weight[i] 的收益，不选取 j 点，相当于割断源点到 j 的边。

当源点和汇点之间没有路径时，就符合题目要求了。而要使总收益最大，就是要求出最小割，因为最大流等于最小割，转化为最大流问题。

不过 dinic 算法的最坏时间复杂度是 O(n^2\times m)，似乎也并不能保证通过……

由于作者很懒，代码就不写了……这个方法的代码可以去看其他人的满分程序。