P4775 [NOI2018] 情报中心 洛谷黑题题解

发布时间:2024年01月24日

[NOI2018] 情报中心

题目描述

C 国和 D 国近年来战火纷飞。

最近,C 国成功地渗透进入了 D 国的一个城市。这个城市可以抽象成一张有 n n n 个节点,节点之间由 n ? 1 n ? 1 n?1 条双向的边连接的无向图,使得任意两个点之间可以互相到达。也就是说,这张无向图实际上是一棵树。

经过侦查,C 国情报部部长 GGB 惊讶地发现,这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这个城市内设立情报机构。情报专家 TAC 在侦查后,安排了 m m m 种设立情报机构的方案。这些方案中,第 i i i 种方案是在节点 x i x_i xi? 到节点 y i y_i yi? 的最短路径的所有边上安排情报人员收集情报,这种方案需要花费 v i v_i vi? 元的代价。

但是,由于人手不足,GGB 只能安排上述 m m m 种方案中的两种进行实施。同时 TAC 指出,为了让这两个情报机构可以更好的合作,它们收集情报的范围应至少有一条公共的边。为了评估一种方案的性能,GGB 和 TAC 对所有的边进行了勘察,给每一条边制定了一个情报价值 c i c_i ci?,表示收集这条边上的情报能够带来 c i c_i ci? 元的收益。注意,情报是唯一的,因此当一条边的情报被两个情报机构收集时,也同样只会有 c i c_i ci? 的收益。

现在,请你帮 GGB 选出两种合法的设立情报机构的方案进行实施,使得这两种方案收集情报的范围至少有一条公共的边,并且在此基础上总收益减去总代价的差最大。

注意,这个值可能是负的,但仍然是合法的。如果无法找到这样的两种方案,请输出 F

输入格式

从文件 center.in 中读入数据。

本题包含多组测试数据。

输入文件的第一行包含一个整数 T T T,表示数据组数;

每组数据包含 ( n + m + 1 ) (n + m + 1) (n+m+1) 行:

1 1 1 行包含一个整数 n n n,表示城市的点数;

2 2 2 到第 n n n 行中,第 ( i + 1 ) (i + 1) (i+1) 行包含三个整数 a i a_i ai? b i b_i bi? c i c_i ci?,表示城市中一条连接节点 a i a_i ai? b i b_i bi?、情报价值为 c i c_i ci? 的双向边,保证 a i < b i a_i < b_i ai?<bi? b i b_i bi? 互不相同;

( n + 1 ) (n + 1) (n+1) 行包含一个整数 m m m,表示 TAC 设立的 m m m 种设立情报机构的方案;

( n + 2 ) (n + 2) (n+2) ( n + m + 1 ) (n + m + 1) (n+m+1) 行中,第 ( n + i + 1 ) (n + i + 1) (n+i+1) 行包含三个整数 x i x_i xi? y i y_i yi? v i v_i vi?,表示第 i i i 种设立情报机构的方案是在节点 x i x_i xi? 到节点 y i y_i yi? 的最短路径上的所有边上安排情报人员收集情报,并且需要花费 v i v_i vi? 元的代价。

输出格式

输出到文件 center.out 中。

输出文件包含 T T T 行;

对于每组数据,输出一行:如果存在合法的方案,则输出一个整数表示最大的总收益减去总代价的差;否则输出 F

样例 #1

样例输入 #1

2
5
1 2 1
2 3 3
3 4 2
1 5 8
2
1 4 5
3 5 8
5
1 2 1
2 3 3
3 4 3
1 5 9
2
1 5 5
2 3 8

样例输出 #1

1
F

样例 #2

样例输入 #2

1
11
1 2 2
1 3 0
2 4 1
3 5 7
1 6 0
1 7 1
1 8 1
6 9 3
4 10 2
4 11 8
10
7 10 2
10 7 0
2 11 1
8 6 7
7 7 0
10 1 1
8 2 1
7 8 3
7 7 3
3 9 9

样例输出 #2

13

提示

样例 1 解释

这个样例中包含两组数据。这两组数据的城市相同,只是在情报的价值和情报机构的方案上有所不同。城市地图如下:

  • 对于第一组数据,方案一中的节点 1 1 1 到节点 4 4 4 的最短路径为 1 → 2 → 3 → 4 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 1234,方案二中的节点 3 3 3 到节点 5 5 5 的最短路径为 3 → 2 → 1 → 5 3 \rightarrow 2 \rightarrow 1 \rightarrow 5 3215。选择这两种方案需要花费 5 + 8 = 13 5 + 8 = 13 5+8=13 的代价,并且每一条边的情报都被收集从而得到 1 + 3 + 2 + 8 = 14 1 + 3 + 2 + 8 = 14 1+3+2+8=14 的收益,因此总收益减去总代价为 14 ? 13 = 1 14 ? 13 = 1 14?13=1
  • 对于第二组数据,方案一中的节点 1 1 1 到节点 5 5 5 的最短路径为 1 → 5 1 \rightarrow 5 15,方案二中的节点 2 2 2 到节点 3 3 3 的最短路径为 2 → 3 2 \rightarrow 3 23。这两种方案收集情报的范围没有公共的边,因此非法,所以这组数据不存在合法方案,应输出 F

样例 2 解释

见附加文件中的 center2.incenter2.ans

这个样例只包含一组数据。这一数据中,最优方案为选择第 2 2 2 种和第 3 3 3 种方案。

这组数据的城市地图如下,其中加粗的边表示被情报中心收集情报的边,红色的边表示只被第 2 2 2 种方案的情报中心收集情报的边,蓝色的边表示只被第 3 3 3 种方案的情报中心收集情报的边,紫色的边表示同时被两个情报中心收集情报的边。

样例 3

见附加文件中的 center3.incenter3.ans

这个样例和第 4 4 4 个测试点的性质相同。每个测试点的性质见下文的表格。

样例 4

由于附加文件大小限制,附加文件不再提供该组样例

见附加文件中的 center4.incenter4.ans

这个样例,无疑是善良的出题人无私的馈赠。大量精心构造的 n ≤ 100 , m ≤ 200 n\le 100,m\le 200 n100,m200 的测试数据,涵盖了测试点中所有出现性质的组合。你可以利用这个测试点,对自己的程序进行全面的检查。足量的数据组数、不大的数据范围和多种多样的数据类型,能让程序中的错误无处遁形。出题人相信,这个美妙的样例,可以给拼搏于 AC 这道题的逐梦之路上的你,提供一个有力的援助。

数据范围

各测试点的数据规模和性质如下表:

测试点 n ≤ n \le n m ≤ m \le m T ≤ 50 T \le 50 T50特殊性质
1 2 2 2 3 3 3保证
2 10 10 10 30 30 30保证
3 200 200 200 300 300 300保证
4 1 0 3 10^3 103 2 , 000 2,000 2,000保证 a i = b i ? 1 a_i = b_i - 1 ai?=bi??1
5 1 0 4 10^4 104 3 × 1 0 4 3 \times 10^4 3×104保证 a i = b i ? 1 a_i = b_i - 1 ai?=bi??1
6 5 × 1 0 4 5 \times 10^4 5×104 3 × 1 0 4 3 \times 10^4 3×104保证 a i = b i ? 1 a_i = b_i - 1 ai?=bi??1
7 1 0 4 10^4 104 3 × 1 0 4 3 \times 10^4 3×104保证 c i = 0 c_i=0 ci?=0
8 5 × 1 0 4 5 \times 10^4 5×104 1 0 5 10^5 105保证 c i = 0 c_i=0 ci?=0
9 5 × 1 0 4 5 \times 10^4 5×104 1 0 5 10^5 105保证 c i = 0 c_i=0 ci?=0
10 1 0 4 10^4 104 n n n保证 S 1 S_1 S1?
11 5 × 1 0 4 5 \times 10^4 5×104 n n n不保证 S 1 S_1 S1?
12 5 × 1 0 4 5 \times 10^4 5×104 n n n不保证 S 1 S_1 S1?
13 1 0 4 10^4 104 3 × 1 0 4 3 \times 10^4 3×104保证 S 2 S_2 S2?
14 1 0 4 10^4 104 3 × 1 0 4 3 \times 10^4 3×104保证 S 2 S_2 S2?
15 5 × 1 0 4 5 \times 10^4 5×104 1 0 5 10^5 105不保证 S 2 S_2 S2?
16 5 × 1 0 4 5 \times 10^4 5×104 1 0 5 10^5 105不保证 S 2 S_2 S2?
17 1 0 4 10^4 104 3 × 1 0 4 3 \times 10^4 3×104保证
18 5 × 1 0 4 5 \times 10^4 5×104$ 10^5$保证
19 5 × 1 0 4 5 \times 10^4 5×104$ 10^5$不保证
20 5 × 1 0 4 5 \times 10^4 5×104$ 10^5$不保证

表格中的特殊性质如下:

  • 特殊性质 S 1 S_1 S1?:对于任意 i , j i, j i,j,保证 x i x_i xi? y i y_i yi? 的最短路径所经过的编号最小的节点不同于 x j x_j xj? y j y_j yj? 的最短路径所经过的编号最小的节点;

  • 特殊性质 S 2 S_2 S2?:对于任意 i i i,保证 x i x_i xi? y i y_i yi? 的最短路径所经过的编号最小的节点为节点 1 1 1

对于所有的数据, 1 ≤ n ≤ 5 × 1 0 4 1 \le n \le 5 \times 10^4 1n5×104 0 ≤ m ≤ 1 0 5 0 \le m \le 10^5 0m105 0 ≤ c i ≤ 1 0 9 0 \le c_i \le 10^9 0ci?109 0 ≤ v i ≤ 1 0 10 × n 0 \le v_i \le 10^{10} \times n 0vi?1010×n。每个测试点中,所有 n n n 的和不会超过 1 ? 000 ? 233 1\,000\,233 1000233,所有 m m m 的和不会超过 2 ? 000 ? 233 2\,000\,233 2000233

_ 这题在NOI2018中可以算是最难的题目了。蒟蒻当然做不来,仅仅是转发一下官方题解。_

题意简述
给出一个 nn 个点的树,每条边上有非负边权
再给出 mm 条树上的链,用端点表示,每条链都有价值
要求选出两条链,满足这两条链至少有一条边相交
最大化选出的链的权值和 + 被至少一条链覆盖的边的边权和
一个测试点可能有很多组数据,n\leq 50,000n≤50,000、m\leq 100,000m≤100,000
测试点内的 nn 和 mm 的和的数量级达到 10^{6}10
6

时间限制 88 秒,空间限制 512512 MB
大暴力
测试点 11、22、33 数据范围非常非常非常小
可以枚举两条链,到树上去统计覆盖的边
O(nm^{2}) = 15’O(nm
2
)=15

聪明的暴力
测试点 11、22、33、44 数据范围有点小
考虑在枚举链的时候加优化
枚举第一条链,把每条边的权值 w(e)w(e) 改成 ↓↓
w’(e) = [ew

(e)=[e在第一条链上]w(e)]w(e)并预处理求出树上距离的数据结构
然后枚举第二条链求树上距离,注意判断是否相交
O(nm) = 20’O(nm)=20

真·暴力
仔细观察数据范围
我们相信出题人为了卡乱搞,不会卡暴力
于是只枚举有公共部分的链
注意使用树链剖分求 LCA 来减小常数
可以通过测试点 1,2,3,4,7,8,9,10,11,12,171,2,3,4,7,8,9,10,11,12,17
55’55

加上一条链的情况可以 65’65

luogu
基于迭代的乱搞♂
前一个暴力中,我们事实上是求出了"确定了一条链后的最大答案"
不难直接把这个过程改成乱搞♂
随机取若干条链分别求答案取 maxmax
随机若干次,每次取一条链,找另一条链使得两条链答案最大,然后从另一条链出发执行操作,迭代多次并在每一步更新答案
把链按照 {链代价,链长度,链经过边数} 的 {-1,0,1?1,0,1} 的系数组合排序,对前面一些链求出这些链的答案
构造数据时,只需要保证每条链的答案接近,这样就能让链交部分的影响扩大到极致,从而卡掉所有这样的迭代乱搞♂
\leq 30’≤30

链的数据
测试点 4,5,64,5,6 中,树是一条链
从而每条链都是一个区间
枚举一条链后,直接用线段树维护即可
O(mO(m loglog n) = 15’n)=15

边权为 00
测试点 4,5,64,5,6 中边权为 00
只需要两条链的权值和最小,链只要相交即可
枚举一条边,求所有经过这条边的链的最大值和次大值,用他们的和更新答案
求经过一条边的链可以用树上差分 + 启发式合并/可并堆完成
O(mO(m loglog n) = 15’n)=15

基于边的乱搞♂
这一个暴力同样也可以改成乱搞♂
对每条边求出经过它的按 {链代价,链长度,链经过边数} 的 {-1,0,1?1,0,1} 的系数组合排序的前若干大,两两之间求答案
然而,前面的构造方法同样可以把这个乱搞♂卡的痛不欲生
\leq 35’≤35

LCA 两两不同 (S_{1})(S
1
?
)
对于 LCA 不同的两条链,两条链的交必然是直上直下的一段
因此可以把一条链拆成两条直上直下的链考虑
在树上枚举较下的交点 (\color{red}\colorbox{white}{红点}
红点
?
)
要求两条链的下端点必须在\color{red}\colorbox{white}{红点}
红点
?
的不同儿子子树中
长度和 + 权值和 - \color{red}\colorbox{white}{红点}
红点
?
深度 + maxmax(\color{green}\colorbox{white}{绿点}
绿点
?
深度, \color{blue}\colorbox{white}{蓝点}
蓝点
?
深度 )
于是可以想到对每个点记 f(i,j)f(i,j)
下端点在 ii 子树内,上端点深度为 jj 的最大的链长度 + 权值
用启发式合并或线段树合并维护这个数组,O(mO(m loglog n) = 30’n)=30

luogu
LCA 全部相同 (S_{2})(S
2
?
)
对于这一部分数据,两条链的交可能不是直上直下的

关键性质 : 链并的两倍 = 两条链长 + \color{blue}\colorbox{white}{蓝点}
蓝点
?
距离 + \color{green}\colorbox{white}{绿点}
绿点
?
距离

那么可以考虑枚举\color{red}\colorbox{white}{红点}
红点
?
,即\color{blue}\colorbox{white}{蓝点}
蓝点
?
的 LCA

要求两个\color{blue}\colorbox{white}{蓝点}
蓝点
?
属于\color{red}\colorbox{white}{红点}
红点
?
不同儿子的子树

这时候要考虑\color{green}\colorbox{white}{绿点}
绿点
?
的距离

如果仍然用深度减去 LCA 深度考虑,无从下手

事实上可以强行树链剖分套线段树维护,但这样太难写

但我们是要最大化\color{green}\colorbox{white}{绿点}
绿点
?
的距离,可以直接从\color{green}\colorbox{white}{绿点}
绿点
?
的最远点对入手 luogu

枚举\color{red}\colorbox{white}{红点}
红点
?
之后,我们的任务是 ↓↓

选出两个属于\color{red}\colorbox{white}{红点}
红点
?
不同儿子子树的\color{blue}\colorbox{white}{蓝点 a,b}
蓝点 a,b
?

使得它们对应\color{green}\colorbox{white}{绿点}
绿点
?
p_{a},p_{b}p
a
?
,p
b
?
的距离 + 两条链链长和权值和 + 两个\color{blue}\colorbox{white}{蓝点}
蓝点
?
深度 -? 22 ×× \color{red}\colorbox{white}{红点}
红点
?
深度最大

注意到\color{red}\colorbox{white}{红点}
红点
?
深度是常数无需考虑

对于其他项,可以通过添加附加点 p_{a}',p_{b}‘p
a

?
,p
b

?
向 p_{a},p_{b}p
a
?
,p
b
?
连接边权为自己所在链长 + 权值的边,转化为找最远点对 p_{a}’,p_{b}'p
a

?
,p
b

?

要求支持集合合并

在合并的时候,求出跨越两个集合的最远点对 luogu

对于非负边权的树,两个点集的并的最远点对的一端,一定是原来两个点集中,某个点集的最远点对的一端,一定是原来两个点集中,某个点集最远点对的一端

只需要对点集记录最远点对端点,即可支持合并

这个算法只需要在树上进行 DFS,以及求 mm 次的 LCA

O(n+m) = 20’O(n+m)=20

满分算法
两条相交的链,要么 LCA 相同,要么 LCA 不同
对于 LCA 不同的所有情况已经可以处理了
对于 LCA 相同的情况,考虑同时处理以每个点为两条链的共同 LCA 的情况
对每个点 pp 记录 f(p,j)f(p,j) 表示在点 pp 处理 LCA 为 jj 时保存的\color{blue}\colorbox{white}{蓝点}
蓝点
?
的集合(记录的是最远点信息)
对 ff 数组进行启发式合并,复杂度 O(n + mO(n+m loglog n)n)
也可以进行点分治,考虑所有过重心的链,转化为全过一个点的情况,复杂度 O(nO(n loglog n+mn+m loglog n)n)
O(n + mO(n+m loglog n)=n)= \color{green}\colorbox{white}{100}
100
?

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 50050
#define MaxM 100500
using namespace std;
const ll INF=1ll<<60;
vector<int> g[MaxN],l[MaxN];
int dep[MaxN],f[16][MaxN]
   ,dfn[MaxN],out[MaxN],id[MaxN<<1],tim;
ll dist[MaxN];
void pfs(int u)
{
  id[dfn[u]=++tim]=u;
  for (int i=0,v;i<g[u].size();i++)
    if (!dfn[v=g[u][i]]){
      dep[v]=dep[f[0][v]=u]+1;
      dist[v]=dist[u]+l[u][i];
      pfs(v);id[++tim]=u;
    }
  out[u]=tim;
}
#define Pii pair<int,int>
#define Pr pair<int,ll>
#define fir first
#define sec second
#define mp make_pair
int lg2[MaxN<<1];
Pii t[18][MaxN<<1];
void Init()
{
  for (int i=2;i<=tim;i++)lg2[i]=lg2[i>>1]+1;
  for (int i=1;i<=tim;i++)t[0][i]=mp(dep[id[i]],id[i]);
  for (int j=1;(1<<j)<=tim;j++)
    for (int i=1;i+(1<<j)-1<=tim;i++)
      t[j][i]=min(t[j-1][i],t[j-1][i+(1<<(j-1))]);
}
int lca(int u,int v){
  u=dfn[u];v=dfn[v];if (u>v)swap(u,v);
  int k=lg2[v-u+1];
  return min(t[k][u],t[k][v-(1<<k)+1]).second;
}
int up(int u,int t){
  int k=15;
  while(k--)while(dep[f[k][u]]>dep[t])u=f[k][u];
  return u;
}
ll dis(int u,int v)
{return dist[u]+dist[v]-2*dist[lca(u,v)];}
inline ll dis(Pr u,Pr v)
{return dis(u.fir,v.fir)+u.sec+v.sec;}
struct Data{Pr u,v;}Z;
ll merge(Data &S,const Data &A,const Data &B)
{
  if (!A.u.fir&&!A.v.fir){S=B;return -INF;}
  if (!B.u.fir&&!B.v.fir){S=A;return -INF;}
  ll ret,mx=-INF,s;int op=-1;
  #define chk(u,v,w) if (u.fir&&v.fir){s=dis(u,v);if (s>mx){mx=s;op=w;}}
  chk(A.u,B.u,3);chk(A.u,B.v,4);
  chk(A.v,B.u,5);chk(A.v,B.v,6);
  ret=mx;
  chk(A.u,A.v,1);chk(B.u,B.v,2);
  if (op==1)S=A;if (op==2)S=B;
  if (op==3)S=(Data){A.u,B.u};if (op==4)S=(Data){A.u,B.v};
  if (op==5)S=(Data){A.v,B.u};if (op==6)S=(Data){A.v,B.v};
  return ret;
}
struct Node{int l,r;Data x;}a[MaxM*40];
int rt[MaxN],tn,to;Pr wfc;
void up(int u){
  if (!a[u].l||!a[u].r){a[u].x=a[a[u].l|a[u].r].x;return ;}
  merge(a[u].x,a[a[u].l].x,a[a[u].r].x);
}
void add(int l,int r,int &u)
{
  if (!u)u=++tn;
  if (l==r){a[u].x.u=wfc;return ;}
  int mid=(l+r)>>1;
  if (to<=mid)add(l,mid,a[u].l);
  else add(mid+1,r,a[u].r);
  up(u);
}
void del(int l,int r,int &u)
{
  if (l==r){a[u].x.u=mp(0,0);return ;}
  int mid=(l+r)>>1;
  if (to<=mid)del(l,mid,a[u].l);
  else del(mid+1,r,a[u].r);
  up(u);
}
int merge(int u,int v)
{
  if (!u||!v)return u|v;
  merge(a[u].x,a[u].x,a[v].x);
  a[u].l=merge(a[u].l,a[v].l);
  a[u].r=merge(a[u].r,a[v].r);
  return u;
}
ll ans;
vector<int> b[MaxN];
int n,m;
void dfs(int u)
{
  for (int i=0,v;i<g[u].size();i++)
    if (dep[v=g[u][i]]>dep[u]){
      dfs(v);
      ans=max(ans,merge(Z,a[rt[u]].x,a[rt[v]].x)-2*dist[u]);
      rt[u]=merge(rt[u],rt[v]);
    }
  for (int i=0;i<b[u].size();i++)
    {to=b[u][i];del(1,m,rt[u]);}
}
void solve()
{
  scanf("%d",&n);
  for (int i=1,u,v,w;i<n;i++){
    scanf("%d%d%d",&u,&v,&w);
    g[u].pb(v);l[u].pb(w);
    g[v].pb(u);l[v].pb(w);
  }dep[1]=1;pfs(1);Init();
  for (int j=1;j<15;j++)
    for (int i=1;i<=n;i++)
      f[j][i]=f[j-1][f[j-1][i]];
  scanf("%d",&m);
  ans=-INF;
  for (int i=1;i<=m;i++){
    int u,v;ll w;
    scanf("%d%d%lld",&u,&v,&w);
    if (u==v)continue;
    w=dis(u,v)-2*w;
    int t=lca(u,v),tu=up(u,t),tv=up(v,t);
    to=i;
    if (u!=t){
      wfc=mp(v,w+dist[u]);
      ans=max(ans,merge(Z,(Data){wfc,mp(0,0)},a[rt[u]].x)-2*dist[u]);
      add(1,m,rt[u]);b[tu].pb(i);
    }
    if (v!=t){
      wfc=mp(u,w+dist[v]);
      ans=max(ans,merge(Z,(Data){wfc,mp(0,0)},a[rt[v]].x)-2*dist[v]);
      add(1,m,rt[v]);b[tv].pb(i);
    }
  }
  dfs(1);
  if (ans<=-INF/10)puts("F");
  else printf("%lld\n",ans/2);
  for (int i=1;i<=n;i++){
    g[i].clear();l[i].clear();b[i].clear();
    dfn[i]=rt[i]=0;
  }memset(a,0,sizeof(Node)*(tn+5));tn=tim=0;
}
int main()
{
  int T;scanf("%d",&T);
  while(T--)solve();
  return 0;
}
文章来源:https://blog.csdn.net/yaosichengalpha/article/details/135829229
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。