城市环路
题目描述
一座城市,往往会被人们划分为几个区域,例如住宅区、商业区、工业区等等。
B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路,环路之内便是 B 市中心。
整个城市可以看做一个 $n$ 个点,$n$ 条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。
现在,有一位名叫 Jim 的同学想在 B 市开店,但是任意一条边的 $2$ 个点不能同时开店,每个点都有一定的人流量,第 $i$ 个点的人流量是 $p_i$,在该点开店的利润就等于 $p_i×k$,其中 $k$ 是一个常数。
Jim 想尽量多的赚取利润,请问他应该在哪些地方开店?
输入格式
第一行一个整数 $n$,代表城市中点的个数。城市中的 $n$ 个点由 $0 \sim n-1$ 编号。
第二行有 $n$ 个整数,第 $(i + 1)$ 个整数表示第 $i$ 个点的人流量 $p_i$。
接下来 $n$ 行,每行有两个整数 $u, v$,代表存在一条连接 $u$ 和 $v$ 的道路。
最后一行有一个实数,代表常数 $k$。
输出格式
输出一行一个实数代表答案,结果保留一位小数。
样例 #1
样例输入 #1
4
1 2 1 5
0 1
0 2
1 2
1 3
2
样例输出 #1
12.0
提示
数据规模与约定
- 对于 $20\%$ 的数据,保证 $n \leq 100$。
- 另有 $20\%$ 的数据,保证环上的点不超过 $2000$ 个。
- 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^5$,$1 \leq p_i \leq 10^4$,$0 \leq u, v < n$,$0 \leq k \leq 10^4$,$k$ 的小数点后最多有 $6$ 位数字。
解题思路
如果这题的图是一棵树的话,那么就是没有上司的舞会这道题。而现在从树变成了基环树,那么就会想到能不能从环上选择一条边删掉变成树来做呢?答案是可以的,假设删除的是环上的边 $(r_1,r_2)$,那么分别以 $r_1$ 和 $r_2$ 为树根跑两遍树形 dp 即可,另外由于边 $(r_1,r_2)$ 最多能选一个节点,因此还要保证 $r_1$ 和 $r_2$ 至多选择其中一个。
定义 $f(u,0)$ 表示以 $u$ 为根的子树中不选节点 $u$ 的所有合法方案的最大权值和,$f(u,1)$ 表示以 $u$ 为根的子树中选择节点 $u$ 的所有合法方案的最大权值和。由题目限制知道如果选择了 $u$,那么其子节点都不能选择,如果不选择 $u$,那么其子节点可选可不选。因此状态转移方程就是 $$\left\{ \begin{array}{l} f(u,0) = \sum\limits_{v \in \text{son}(u)}{\max\{ f(v,0), \, f(v,1) \}} \\ f(u,1) = \sum\limits_{v \in \text{son}(u)}{f(v,0)} \end{array} \right.$$
另外可以通过并查集来得到环上的某条边,当枚举到边 $(r_1,r_2)$ 并且两个节点属于同一个连通块中,说明加上这条边就会形成一个环,因此 $(r_1,r_2)$ 就是环上的一条边。
为什么要分别对 $r_1$ 和 $r_2$ 跑一遍树形 dp?如果只对 $r_1$ 求一次那么当 $f(u,0) < f(u,1)$ 时无法保证最优解 $f(u,1)$ 不选 $r_2$,因此还需要知道 $f(r_2,0)$,那么最终答案就是 $\max \{ f(r_1,0), \, f(r_2,0) \}$(因为至少有一个节点不选)。是否还需要考虑删除环上其他的边并重复这个过程?没有必要,因为只需对边 $(r_1,r_2)$ 求一次就知道取最优解时 $r_1$ 和 $r_2$ 的状态,考虑其他边的最优解时 $r_1$ 和 $r_2$ 还是这个状态。
AC 代码如下,时间复杂度为 $O(n)$:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int w[N];
int head[N], e[M], ne[M], idx;
int f[N][2];
int fa[N];
void add(int u, int v) {
e[idx] = v, ne[idx] = head[u], head[u] = idx++;
}
int find(int x) {
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void dfs(int u, int pre) {
f[u][0] = 0, f[u][1] = w[u];
for (int i = head[u]; i != -1; i = ne[i]) {
if (e[i] != pre) {
dfs(e[i], u);
f[u][0] += max(f[e[i]][0], f[e[i]][1]);
f[u][1] += f[e[i]][0];
}
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", w + i);
}
memset(head, -1, sizeof(head));
for (int i = 0; i < n; i++) {
fa[i] = i;
}
int r1, r2;
for (int i = 0; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
if (find(u) == find(v)) {
r1 = u, r2 = v;
}
else {
fa[find(u)] = find(v);
add(u, v), add(v, u);
}
}
dfs(r1, -1);
int ret = f[r1][0];
dfs(r2, -1);
ret = max(ret, f[r2][0]);
double m;
scanf("%lf", &m);
printf("%.1f", ret * m);
return 0;
}
参考资料
P1453 城市环路 题解:https://www.luogu.com.cn/blog/xcxc82/post-p1453-cheng-shi-huan-lu-ti-xie
标签:环路,head,环上,leq,int,城市,fa,find From: https://www.cnblogs.com/onlyblues/p/17818288.html