P8817 题解

先行吐槽：数据过水，一个重大的错误竟然得了

80

分。

题目大意

给定

n , m , k

、

2 \sim n

这

n - 1

个点的分数，和一张

n

个点

m

条边的无向图（无自环、重边）。你必须恰好选择四个不同于

1

且互不相同的点，并按一定顺序将其排列好，设四个点按顺序分别为

a , b , c , d

，则要求

1 \rightarrow a

、

a \rightarrow b

、

b \rightarrow c

、

c \rightarrow d

、

d \rightarrow 1

这五段的距离均小于等于

k + 1

（即除每段的起点和终点外，最多额外经过

k

个点）。要求最大化

a , b , c , d

四个点的分数之和。

题目思路

下面记

a , b , c , d

分别为第一、二、三、四个点，并且我们认为两点距离大于

k + 1

时这两点不可互相到达。

~~首先不能四个点全枚举，不然这题还有啥意思。而且显然贪心是错的，不然这题还有啥意思。~~

既然边长固定为

1

，那直接

n

次 BFS 把全源最短路求出来，时间复杂度

O(n ^ 2)

，这里不说了。

观察数据范围可得，我们只能枚举两个点，对于剩下的两个点，我们需要用常数次枚举找到最优答案。

当然枚举两个点也足够了。我们发现，

a

、

d

两个点都需要可以到达

1

，我们可以花

O(n)

的时间把

1

可以到达的点找到，同样也是这些点可以到达

1

。而对于

b , c

两个点，我们必须

O(n ^ 2)

枚举这两个点，原因也很显然：贪心是错的。

但我们既然要枚举这两个点，就需要在常数时间内找到

a , d

两点。既然上文可以

O(n)

时间内求出一个点能否到达

1

，那不妨对于每一组

(x , y)

，求出能否同时满足

x

和

1

互相可达且

x

和

y

互相可达。我们已经求出最短路了，这部分也很简单。

那么我们都能处理出来每个点可到达的点中，可以到达

1

的所有点了，肯定不能把所有这些信息全都保留下来，不然最坏情况下和直接枚举是没有区别的。显然对于一个点，我们并不需要存下所有同时可以到达这个点和

1

的所有点，而是只需要分数前若干大的点。不妨假设我们现在在考虑

b

点可到达的

a

点，那么

a

点不能和

c , d

两点相同。如果分数前两大的

a

点分别是最终选择的

c , d

两点，我们就需要再记录下分数第三大的

a

点。而这个过程中不需要额外考虑

1

这个点，因为我们可以手动将它的分数设置为

-\infin

，本题中取小于等于

- 4 \times {10} ^ {18}

的数字即可。

综上所述，我们需要在枚举每一组

(x , y)

是否符合“

x

和

1

互相可达且

x

和

y

互相可达”的基础上，动态维护可同时到达某个点和

1

这个点的分数前三大，而这个信息可以用 set 动态维护。

然后就做完了。注意最好不要维护分数第四大及以后的值，因为没用，而且可能过不了。

题目代码

~~没啥好说的，我觉得这题不难理解。~~

~~代码缺省源这种东西自己看着来吧。~~

~~又附：一开始我把分数放到第二关键字排序，怒提 $80$ 分。~~

CPP

long long n , m , k;
long long sc[2505]; // score
vector < long long > v[2505];
long long dist[2505][2505];
void bfs(int st)
{
	vector < bool > vis(n + 1 , 0);
	queue < pair < long long , long long > > q;
	q.push(make_pair(st , 0));
	while(q.size())
	{
		pair < long long , long long > a = q.front();
		q.pop();
		if(vis[a.first])
		{
			continue;
		}
		vis[a.first] = 1;
		dist[st][a.first] = a.second;
		for(int i : v[a.first])
		{
			q.push(make_pair(i , a.second + 1));
		}
	}
}
set < pair < long long , long long > > max_get[2505]; // 每个点能到的点中，能回到 1 的点的最大点权 
signed main()
{
	read(n , m , k);
	sc[1] = -LONG_LONG_MAX; 
	for(int i = 2 ; i <= n ; i++)
	{
		read(sc[i]);
	}
	for(int i = 1 ; i <= m ; i++)
	{
		int x , y;
		read(x , y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	memset(dist , 0x3f , sizeof(dist));
	for(int i = 1 ; i <= n ; i++)
	{
		bfs(i);
	}
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			if(dist[j][1] <= k + 1 && dist[i][j] <= k + 1)
			{
				max_get[i].insert(make_pair(sc[j] , j));
			}
			if(max_get[i].size() > 3)
			{
				max_get[i].erase(max_get[i].begin());
			}
		}
	}
	long long ans = 0;
	for(int i = 2 ; i <= n ; i++)
	{
		for(int j = 2 ; j <= n ; j++)
		{
			if(dist[i][j] > k + 1 || i == j)
			{
				continue;
			}
			for(pair < long long , long long > x : max_get[i])
			{
				for(pair < long long , long long > y : max_get[j])
				{
					int p1 = x.second , p2 = y.second;
					long long s1 = x.first , s2 = y.first;
					if(i == p1 || j == p1 || i == p2 || j == p2 || p1 == p2 || p1 == 1 || p2 == 1)
					{
						continue;
					}
					ans = max(ans , s1 + s2 + sc[i] + sc[j]);
				}
			}
		}
	}
	printnl(ans);
	return 0;
};

*P8817 题解

文章操作