自动搬运

查看原文

来自洛谷，原作者为

	dingyichen **

搬运于2025-08-24 22:27:56，当前版本为作者最后更新于2024-03-15 17:18:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

随机跳题跳到了这一题，发现一个 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)$，似乎也并不能保证通过……

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