差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/23 10:16]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-===== B. Best Subgraph =====
+===== H. travel =====
 ==== 题意 ====
-定义 $k-\text{degree}$ 子图为每个点在子图中度数至少为 $k$ 的连通极大子图。
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
-定义每个 $G$ 的子图 $S$ 的分数为 $M\times m(S)-N\times n(S)+B\times b(S)$。
-其中 $m(S)$ 表示 $S$ 的边数，$n(S)$ 表示 $S$ 的点数，$b(S)$ 表示 $|\{(u,v)|(u,v)\in G,u\in S,v\not\in S\}|$。
-求分数最大的 $k-\text{degree}$ 子图，并求出分数最大的 $k-\text{degree}$ 子图中 $k$ 的最大值。
-输入保证图连通。
 ==== 题解 ====
-首先，定义 $V(k)$ 表示所有 $k-\text{degree}$ 子图的并集，易知 $V(k+1)\subseteq V(k)$。
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
-构建分层图，其中第 $k$ 层的点集为 $V(k)-V(k+1)$，同时对每个点 $u\in V(k)-V(k+1)$，$w(u)=k$。
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
-然后考虑按层加点，动态维护当前每个 $k-\text{degree}$ 子图的答案。对于每个新加入的点 $u$，首先他本身产生贡献 $-N$。
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
-对于 $u$ 的所有连边 $(u,v)$，如果 $w(v)\gt w(u)$，则 $(u,v)$ 会被加入 $m(S)$，同时从 $b(S)$ 删除，产生贡献 $M-B$。
+考虑状态转移，利用生成链的合并，不难有
-如果 $w(v)=w(u)$，则 $(u,v)$ 也会被加入 $m(S)$，但为了贡献被计算两次，于是每个点的贡献为 $\frac M2$。
+$$
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
+$$
-如果 $w(v)\lt w(u)$，则 $(u,v)$ 会被加入 $b(S)$，产生贡献 $B$。
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
-于是上述过程可以将所有贡献都转化为每个点的点权。考虑加入点时并查集维护每个连通块的点权和。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
-每层点全部加完后查询每个连通块的点权和的最大值即为所有 $k-\text{degree}$ 子图的最大答案。
+$$
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
+$$
-至于如果计算每个点的 $w(u)$。首先输入保证图连通，所有图 $G$ 本身就是 $1-\text{degree}$ 子图。
+最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。
-考虑先删去所有度数为 $1$ 的点，删点后可能会导致原来度数不为 $1$ 的点度数不大于 $1$，继续删除，直到无点可删，得到 $2-\text{degree}$ 子图。
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
-将删去的点的 $w(u)$ 全部设为 $1$，然后再求  $3-\text{degree}$ 子图不断重复上述过程，即可得到所有 $w(u)$。
-时间复杂度 $O\left(\text{Na}(n+m)\right)$。
 <hidden 查看代码>
 <code cpp>
-const int MAXN=1e6+5;
+const int MAXN=4e5+5,MAXK=4;
-const LL inf=1e18;
 struct Edge{
 	int to,next;
 }edge[MAXN<<1];
-int head[MAXN],edge_cnt;
+int a[MAXN],head[MAXN],edge_cnt;
+LL dp[MAXN][3][MAXK],tmp[3][MAXK];
 void Insert(int u,int v){
 	edge[++edge_cnt]=Edge{v,head[u]};
 	head[u]=edge_cnt;
 }
-bool vis[MAXN];
+void Max(LL &a,LL b){
-vector<int> q[MAXN],vec[MAXN];
+	if(b>a)
-int deg[MAXN],w[MAXN],p[MAXN];
+	a=b;
-LL sum[MAXN];
+}
-int Find(int x){
+void dfs(int u,int fa){
-	return x==p[x]?x:p[x]=Find(p[x]);
+	dp[u][1][0]=a[u];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+		_for(i,0,3)_for(j,0,MAXK)
+		tmp[i][j]=dp[u][i][j];
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
+		}
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
+	}
+	_for(i,1,MAXK)
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
 }
 int main()
 {
-	int n=read_int(),m=read_int(),M=read_int(),N=read_int(),B=read_int();
+	int n=read_int();
-	while(m--){
+	_rep(i,1,n)
+	a[i]=read_int();
+	_for(i,1,n){
 		int u=read_int(),v=read_int();
 		Insert(u,v);
 		Insert(v,u);
-		deg[u]++;
-		deg[v]++;
-	}
-	_rep(i,1,n)
-	q[deg[i]].push_back(i);
-	_for(k,1,MAXN){
-		_for(j,0,q[k].size()){
-			int u=q[k][j];
-			if(vis[u])continue;
-			vis[u]=true;
-			w[u]=k;
-			vec[k].push_back(u);
-			for(int i=head[u];i;i=edge[i].next){
-				int v=edge[i].to;
-				deg[v]--;
-				q[deg[v]].push_back(v);
-			}
-		}
-	}
-	_rep(u,1,n){
-		p[u]=u;
-		sum[u]=-N;
-		for(int i=head[u];i;i=edge[i].next){
-			int v=edge[i].to;
-			if(w[u]<w[v]){
-				sum[u]+=M;
-				sum[u]-=B;
-			}
-			else if(w[u]==w[v]&&u<v)
-			sum[u]+=M;
-			else if(w[u]>w[v])
-			sum[u]+=B;
-		}
-	}
-	int st=MAXN-1;
-	while(vec[st].empty())st--;
-	pair<LL,int> ans=make_pair(-inf,0);
-	for(int k=st;k;k--){
-		for(int u:vec[k]){
-			for(int i=head[u];i;i=edge[i].next){
-				int v=edge[i].to;
-				if(w[v]<k)continue;
-				int x=Find(u),y=Find(v);
-				if(x!=y){
-					p[x]=y;
-					sum[y]+=sum[x];
-				}
-			}
-		}
-		for(int u:vec[k])
-		ans=max(ans,make_pair(sum[Find(u)],k));
 	}
-	space(ans.second);enter(ans.first);
+	dfs(1,0);
+	enter(dp[1][0][3]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具