PerfectPan
;

HDUOJ 6268 Master of Subgraph

April 16, 2018

题目链接http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

题意:给你一棵树,每个节点有自己的价值 wiw_i,给定一个数字 mm,问 1m1-mmm 个数字是否能用一个联通子图的价值和表示出来,能输出 11 否则输出 00

思路:先不考虑联通子图这个问题,那么整个问题就是一个裸的树形背包问题,我们把树的 dfsdfs 序建立出来,对于 dfsdfs 序上的每一个点,考虑如果自己选那么自己子树内就可以选,否则只有在这棵子树外面才可以选。设 dp[i][j]dp[i][j]dfsdfs 序上 [i,n][i,n] 位置对应的节点背包容量为 jj 是否能被表示出来,对于位置 ii,如果选我们就从 dp[i+1]dp[i+1] 转移过来,不选我们就从 dp[i+sz[id[i]]]dp[i+sz[id[i]]] 这个位置转移过来,id[i]id[i] 表示 dfsdfs 序为 ii 的节点编号是什么,sz[id[i]]sz[id[i]] 表示这个节点的子树大小是多少,从后往前进行 dpdp,最终 dp[1]dp[1] 就是以 xx 为根的树形背包的答案。考虑到需要联通子图,不能是一块一块的,我们即用点分治,每次求出包含重心的答案,然后递归下去即可,由于这里的 mm 很大,所以 0101 背包要用 bitsetbitset 优化,时间复杂度 O(nmlogn64)O(\frac{nmlogn}{64})

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair 
using namespace std;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
const int N=3000+10;
int T,n,m,u,v,i,root,tot,sum,f[N],w[N],sz[N],sz2[N],val[N],id[N];
bool vis[N];
vector<int>G[N];
bitset<100005>g[N],res;
void getroot(int u,int fa){
	sz[u]=1,f[u]=0;
	for (int i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (v==fa || vis[v]) continue;
		getroot(v,u);
		sz[u]+=sz[v];
		f[u]=max(f[u],sz[v]);
	}
	f[u]=max(f[u],sum-sz[u]);
	if (f[u]<f[root]) root=u;
}
void dfs(int u,int fa){
	sz2[u]=1,val[++tot]=u,id[u]=tot;
	for (int i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (v==fa || vis[v]) continue;
		dfs(v,u);
		sz2[u]+=sz2[v];
	}
}
void solve(int u){
	vis[u]=1,tot=0,dfs(u,0);
	int i;
	for (i=1;i<=tot+1;i++) g[i].reset();
	g[tot+1].set(0);
	for (i=tot;i>=1;i--){
		int u=val[i];
		g[i]|=g[i+1]<<w[u];
		g[i]|=g[i+sz2[u]];
	}
	res|=g[1];
	for (i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (vis[v]) continue;
		sum=sz[v],root=0;
		getroot(v,0);
		solve(root);
	}
}
int main(){
	for (read(T);T--;){
		read(n),read(m);
		for (i=1;i<=n;i++) G[i].clear(),vis[i]=0;
		for (i=1;i<n;i++){
			read(u),read(v);
			G[u].PB(v);
			G[v].PB(u);
		}
		for (i=1;i<=n;i++) read(w[i]);
		res.reset(),sum=n,root=0,f[0]=n+1;
		getroot(1,0);
		solve(root);
		for (i=1;i<=m;i++) printf("%d",res[i]?1:0);
		puts(""); 
	}
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.