【题目来源】
https://www.luogu.com.cn/problem/P1453
【题目描述】
一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。
B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路，环路之内便是 B 市中心。
整个城市可以看做一个 n 个点，n 条边的单圈图（保证图连通），唯一的环便是绕城的环路。保证环上任意两点有且只有 2 条简单路径互通。图中的其它部分皆隶属城市郊区。
现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 2 个点不能同时开店，每个点都有一定的人流量，第 i 个点的人流量是 pi，在该点开店的利润就等于 pi×k，其中 k 是一个常数。
Jim 想尽量多的赚取利润，请问他能获取的利润最大为多少？
【输入格式】
第一行一个整数 n，代表城市中点的个数。城市中的 n 个点由 0∼n−1 编号。
第二行有 n 个整数，第 (i+1) 个整数表示第 i 个点的人流量 pi。
接下来 n 行，每行有两个整数 u，v，代表存在一条连接 u 和 v 的道路。
最后一行有一个实数，代表常数 k。
【输出格式】
输出一行一个实数代表答案，结果保留一位小数。
【输入样例】
4
1 2 1 5
0 1
0 2
1 2
1 3
2
【输出样例】
12.0
【数据范围】
对于 20% 的数据，保证 n≤100。
另有 20% 的数据，保证环上的点不超过 2000 个。
对于 100% 的数据，保证 1≤n≤10^5，1≤pi≤10^4，0≤u, v<n，0≤k≤10^4，k 的小数点后最多有 6 位数字。
【算法分析】
● 基环树：https://blog.csdn.net/hnjzsyjyj/article/details/167919947
● 这是一个纯环，没有挂树。环上每个点权值即城市的人流量。约束是环形最大权独立集。
标准做法：断边法。删掉环边，分两次做线性 DP。
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e5+5; vector<int> g[N]; int pre[N],p[N]; double f[N][2]; int ru,rv; int n; int find(int x) { if(x!=pre[x]) pre[x]=find(pre[x]); return pre[x]; } void dfs(int u,int fa) { f[u][1]=p[u]; f[u][0]=0; for(int v:g[u]) { if(v==fa) continue; dfs(v,u); f[u][1]+=f[v][0]; f[u][0]+=max(f[v][0],f[v][1]); } } int main() { cin>>n; for(int i=0; i<n; i++) cin>>p[i]; for(int i=0; i<n; i++) pre[i]=i; for(int i=0; i<n; i++) { int u,v; cin>>u>>v; int fu=find(u),fv=find(v); if(fu!=fv) { pre[fu]=fv; g[u].push_back(v); g[v].push_back(u); } else ru=u, rv=v; } double k; cin>>k; dfs(rv,-1); double ans1=f[rv][0]; dfs(ru,-1); double ans2=f[ru][0]; double res=max(ans1,ans2)*k; printf("%.1lf\n",res); return 0; } /* in: 4 1 2 1 5 0 1 0 2 1 2 1 3 2 out: 12.0 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/167986230
https://blog.csdn.net/hnjzsyjyj/article/details/167918148
https://blog.csdn.net/hnjzsyjyj/article/details/167919947
