题解 P1453 【城市环路】

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

题目链接：城市环路。

关于题目：一道比较显然的 基环树 上的 dp 题。

应用算法：树形 dp \(+\) 环形 dp。

写在前面：

\(\qquad\!\!\)本来题解区有一篇和我的思路一样的题解，不过那篇题解写得并不对，并不能通过我为这道题添加的 hack 数据。由于我个人认为这个思路对于基环树的初学者思维难度较小，比较友好，所以就有了这篇题解。

\(\qquad\!\!updata\ \ 2020.10.6\)：修改了之前挂错的链接；增加时空复杂度分析。

\(\qquad\!\!updata\ \ 2020.10.25\)：修改了之前对于 环形 dp 的初始化的一个错误。感谢 @pigstd 指出。

下面进入正文：

  • 一、分析题意：

\(\qquad\!\!n\) 个点 \(n\) 条边、全部联通且只有一个环，满足这些条件的图很显然是一棵基环树。

\(\qquad\!\!\)每个点有点权且任意相邻的两个点不能同时选取，很显然我们需要进行类似于没有上司的舞会的 dp。

  • 二、dp 过程：

    \(\qquad\!\!\)和其它题解不一样的，我的 dp 过程主要是利用基环树的一个性质将该问题分解为两个子问题逐一解决。

    \(\qquad\!\!\)由于一棵基环树可以看作一棵树加了一条非重边在图上形成了唯一一个环，那么我们可以将该环上的每个点看作一个根节点，在不考虑环上的点与之联通的情况下，每个根节点都联通出一棵树。也就是说，一棵基环树等价于很多棵树的根节点被连在了一个环上的一张图。

    \(\qquad\!\!\)由此，我们便可以将这个问题分解为以环上的点为根节点的很棵多树的 树形 dp \(+\) 这些环上的点的 环形 dp。

    \(\qquad\!\!\)具体过程如下：

    • 1、找环：

    \(\qquad\!\!\)我利用的是拓扑排序 \(+\) dfs 的方式进行找环。

    \(\qquad\!\!\)首先，对于所有节点拓扑排序一遍，而后入度为 \(2\) 的点就是环上的点。

    \(\qquad\!\!\)其次，任意选择一个环上的点（我选择的就是编号最小的节点）进行 dfs。

    \(\qquad\!\!\)最后，每次 dfs 到一个 未被记录入环并且入度为 \(2\) 的节点，将其记录入环并进行递归。

    \(\qquad\!\!\)可能有同学要问：为什么不能直接拓扑排序后每个点一次循环一遍入度为 \(2\) 就记录入环而要区 dfs 呢？

    \(\qquad\!\!\)那是因为我们之后需要进行 环形 dp，需要保证环上依次连续的点在图上也是依次连续的，所以不能只进行一个简简单单的循环而需要 dfs。

    • 2、树形 dp：

    \(\qquad\!\!\)即对于每棵树都进行一次没有上司的舞会的 dp 过程：

    \(\qquad\!\!\)设 \(f_{i,0}\) 表示 \(i\) 点不选择，\(i\) 点子树的最大贡献；\(f_{i,1}\) 表示 \(i\) 点选择，\(i\) 点子树的最大贡献。对于每个点 \(i\)，\(f_{i,0}\) 的初始值为 \(0\)，\(f_{i,1}\) 的初始值即为题目中的每个点的人流量 \(p_i\)。

    \(\qquad\!\!\)转移方程（\(v\) 点为 \(u\) 点的子节点）：

    \(\qquad\!\!f_{u,0}\gets f_{u,0}+\max(f_{v,0},f_{v,1})\)

    \(\qquad\!\!f_{u,1}\gets f_{u,1}+f_{v,0}\)

    • 3、环形 dp：

    \(\qquad\!\!\)没有接触过 环形 dp 的同学可以左转先看一下这两道题：P6064 [USACO05JAN]Naptime G 和 SP283 NAPTIME - Naptime。

    \(\qquad\!\!\)由于此时每棵树内部节点的关系均已满足题目的限定，剩下的就是环上的各个节点之间的关系，那么我们只需要对每棵树的根节点进行一次 环形 dp 即可得出答案。

    \(\qquad\!\!\)设 \(c_i\) 为环上第 \(i\) 个点的编号，\(tot\) 为环上的节点总数。

    \(\qquad\!\!\)那么此时 \(f_{c_i,0}\) 代表以 \(c_i\) 为根的树不选 \(c_i\) 最大贡献； \(f_{c_i,1}\) 代表以 \(c_i\) 为根的树选 \(c_i\) 最大贡献。

    \(\qquad\!\!\)设 \(g_{i,0}\) 表示点 \(c_i\) 不选，前 \(i\) 个节点的最大贡献，设 \(g_{i,1}\) 表示点 \(c_i\) 选，前 \(i\) 个节点的最大贡献。

    \(\qquad\!\!\)转移方程：

    \(\qquad\!\!g_{i,0}\gets \max(g_{i-1,0},g_{i-1,1})+f_{c_i,0}\)

    \(\qquad\!\!g_{i,1}\gets g_{i-1,0}+f_{c_i,1}\)

    \(\qquad\!\!\)由于是进行 环形 dp，为了枚举全面所有的情况，我们需要进行两次 dp 过程：

    \(\qquad\!\!\)①、规定 \(c_1\) 节点一定不选：

    \(\qquad\!\!\qquad\!\!\)初始化 \(g\) 中的每一个元素为 \(-inf\)；\(g_{1,0}=f_{c_1,0}\)。

    \(\qquad\!\!\qquad\!\!\)进行 dp，统计答案 \(ans=\max(g_{tot,0},g_{tot,1})\)。

    \(\qquad\!\!\)②、规定 \(c_1\) 节点一定选：

    \(\qquad\!\!\qquad\!\!\)初始化 \(g\) 中的每一个元素为 \(-inf\)；\(g_{1,1}=f_{c_1,1}\)。

    \(\qquad\!\!\qquad\!\!\)进行 dp，统计答案 \(ans=\max(ans,g_{tot,0})\)。

  • 三、复杂度分析：

    • 时间复杂度：无论是在找环还是在两次 dp 的过程中，每个点最多被经过一次，所以时间复杂度为 \(O(n)\)。

    • 空间复杂度：由几个数组的定义可知，每个数组所用的空间均为 \(O(n)\) 的数量级，所以总空间复杂度为 \(O(n)\)。

  • 四、最后，上代码（码风不喜勿喷）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
//P1453 城市环路
#include<bits/stdc++.h>
#define in inline
#define re register
#define N 100010
using namespace std;
int n;
int cnt,head[N];
struct edge
{
	int to,nxt;
};
edge e[N<<1];
bool b[N];
int tot;
int rd[N],c[N];
int f[N][2],g[N][2];
int ans;
double k;
in int qread()
//快读
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void mr(re int u,re int v)
//建边
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	return ;
}
in void dfs0(re int u,re int fa)
//找环
{
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
        //父节点或已在环上就不算
		if(v==fa||b[v])
		{
			continue;
		}
        //找到一个点就加入环
		if(rd[v]==2)
		{
			b[v]=1;
			c[++tot]=v;
            //递归
            dfs0(v,u);
            //加入一个点后就跳出循环
			break;
		}
	}
    return ;
}
in void tppx()
//拓扑排序
{
	queue<int> q;
	for(re int i=1;i<=n;i++)
	{
		if(rd[i]==1)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(re int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			rd[v]--;
			if(rd[v]==1)
			{
				q.push(v);
			}
		}
	}
	for(re int i=1;i<=n;i++)
	{
        //找到第一个在环上的点加入环并进行 dfs
		if(rd[i]==2)
		{
			b[i]=1;
			c[++tot]=i;
			dfs0(i,0);
            //加入一个点后就跳出循环
			break;
		}
	}
	return ;
}
in void dfs(re int u,re int fa)
//树形 dp
{
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa||b[v])
        //父节点或已在环上就不算
		{
			continue;
		}
		dfs(v,u);
        //转移
		f[u][0]+=max(f[v][1],f[v][0]);
		f[u][1]+=f[v][0];
	}
	return ;
}
int main()
{
    //读入
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		f[i][1]=qread();
	}
	for(re int i=1;i<=n;i++)
	{
		int u=qread()+1;
		int v=qread()+1;
        //统计入度
		rd[u]++;
		rd[v]++;
        //建边
		mr(u,v);
		mr(v,u);
	}
    //拓扑排序
	tppx();
    //对于每棵树 树形 dp
	for(re int i=1;i<=tot;i++)
	{
		dfs(c[i],0);
	}
    //环形 dp
	memset(g,-0x3f,sizeof(g));
	g[1][0]=f[c[1]][0];
	for(re int i=2;i<=tot;i++)
	{
		g[i][1]=g[i-1][0]+f[c[i]][1];
		g[i][0]=max(g[i-1][0],g[i-1][1])+f[c[i]][0];
	}
	ans=max(g[tot][0],g[tot][1]);
	memset(g,-0x3f,sizeof(g));
	g[1][1]=f[c[1]][1];
	for(re int i=2;i<=tot;i++)
	{
		g[i][1]=g[i-1][0]+f[c[i]][1];
		g[i][0]=max(g[i-1][0],g[i-1][1])+f[c[i]][0];
	}
	ans=max(ans,g[tot][0]);
    //读入 k
	scanf("%lf",&k);
    //输出答案
	printf("%.1lf\n",ans*k);
	return 0;
}