一类经典的树形染色问题

本文主要是介绍一类经典的树形染色问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

1. 2种做法，一种是 $O(nk\log n)$，另一种是 $O(n)$。前者可以从深度大的开始填（优先队列维护）。后者只需要开 $f[0][x]$ 表示 $x$ 离关键点的最近距离，$f[1][x]$ 表示 $x$ 离没被控制的最远点的距离。考虑 $f[0][x]+f[1][x] \le k$ ，$x$ 就能被控制。$f[1][x]=k$，$x$ 就要成为关键点。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9  
10 #define ll long long
11  
12 using namespace std;
13 int rd() {
14     int f=1,sum=0; char ch=getchar();
15     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
16     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
17     return sum*f;
18 }
19 ll lrd() {
20     ll f=1,sum=0; char ch=getchar();
21     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
23     return sum*f;
24 }
25 
26 const int N=(int)(1e5+5);
27 struct edge {
28     int nex,to;
29 }e[N<<1];
30 struct node {
31     int val,id;
32     bool operator < (const node &x) const {
33         return val<x.val;
34     }
35     bool operator > (const node &x) const {
36         return val>x.val;
37     }
38 };
39 priority_queue<node>q;
40 bool vis[N];
41 int head[N],cnt,dep[N],fa[N];
42 int n,m;
43 
44 void add_edge(int x,int y) {
45     e[++cnt]=(edge){head[x],y}; head[x]=cnt;
46 }
47 
48 void dfs1(int x,int ff) {
49     for(int i=head[x];i;i=e[i].nex) {
50         int y=e[i].to;
51         if(dep[y]) continue;
52         fa[y]=x; dep[y]=dep[x]+1;
53         dfs1(y,x);
54     }
55 }
56 
57 void dfs2(int x,int ff,int num) {
58     //cout<<x<<" "<<num<<endl;
59     vis[x]=1; if(!num) return ;
60     for(int i=head[x];i;i=e[i].nex) {
61         int y=e[i].to;
62         if(y==ff) continue;
63         dfs2(y,x,num-1);
64     } 
65 }
66 
67 int main() {
68     int x,y;
69     n=rd(); m=rd(); rd();
70     for(int i=1;i<n;i++) {
71         x=rd(); y=rd(); add_edge(x,y); add_edge(y,x);
72     }
73     fa[1]=1; dep[1]=1; dfs1(1,1);
74     for(int i=1;i<=n;i++) q.push((node){dep[i],i});
75     int ans=0;
76     while(!q.empty()) {
77         int x=q.top().id; q.pop();
78         if(vis[x]) continue;
79         vis[x]=1; ++ans; 
80         for(int i=1;i<=m;i++) x=fa[x];
81         dfs2(x,x,m);
82     }
83     printf("%d",ans);
84     return 0;
85 }

View Code

2. 考虑二分，然后把非关键点就不要计入贡献，即只需要让这些非关键点满足$f[0][x]+f[1][x] \le k$ 即可。那么初始化改下 $f[1]$ 就好。 dp 过程对于关键点的 $f[1]$ 要对 0 取个max。即也许最远没被控制的是它自己。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 
10 #define ll long long
11 
12 using namespace std;
13 int rd() {
14     int f=1,sum=0; char ch=getchar();
15     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
16     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
17     return sum*f;
18 }
19 ll lrd() {
20     ll f=1,sum=0; char ch=getchar();
21     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
23     return sum*f;
24 }
25 // f[0][x] x到关键点的最小距离 f[1][x] x到最远未控制点的距离 
26 const int N=(int)(3e5+5);
27 struct edge {
28     int nex,to;
29 }e[N<<1];
30 int f[2][N],col[N],head[N],cnt,n,m,K,ans;
31 
32 void add_edge(int x,int y) {
33     e[++cnt]=(edge){head[x],y}; head[x]=cnt;
34 }
35 
36 void dfs(int x,int ff) {
37     for(int i=head[x];i;i=e[i].nex) {
38         int y=e[i].to;
39         if(y==ff) continue;
40         dfs(y,x);
41         f[1][x]=max(f[1][x],f[1][y]+1);
42         f[0][x]=min(f[0][x],f[0][y]+1);
43     }
44     if(col[x]) f[1][x]=max(f[1][x],0);
45     if(f[0][x]+f[1][x]<=K) f[1][x]=-0x3f3f3f3f;
46     if(f[1][x]==K) {
47         f[1][x]=-0x3f3f3f3f; f[0][x]=0; ++ans;
48     } 
49     if(x==1) if(f[0][x]+f[1][x]>K) ++ans;
50 }
51 
52 bool check(int x) {
53     memset(f[0],0x3f,sizeof(f[0])); memset(f[1],-0x3f,sizeof(f[1]));
54 //    cout<<f[1][0]<<endl;
55     K=x; ans=0;
56     dfs(1,0);
57     return ans<=m; 
58 }
59 
60 int main() {
61     int x,y;
62     n=rd(); m=rd();
63     for(int i=1;i<=n;i++) col[i]=rd();
64     for(int i=1;i<n;i++) {
65         x=rd(); y=rd(); add_edge(x,y); add_edge(y,x); 
66     }
67     int l=0,r=n,res=0;
68     while(l<=r) {
69         int mid=(l+r)>>1;
70         if(check(mid)) res=mid,r=mid-1;
71         else l=mid+1;
72     } 
73     printf("%d",res);
74     return 0;
75 }

View Code

3. 树形 dp，solution 在注释里面。至于为什么 k 要正序枚举，因为一开始的时候必须加上子树全为白色情况。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 
10 #define ll long long
11 
12 using namespace std;
13 int rd() {
14     int f=1,sum=0; char ch=getchar();
15     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
16     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
17     return sum*f;
18 }
19 ll lrd() {
20     ll f=1,sum=0; char ch=getchar();
21     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22     while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
23     return sum*f;
24 }
25 /*
26 f[x][k] 表示在x点 其中x的子树有k个黑点 sz[x]-k个白点的最大收益
27 ans=f[1][k]
28 考虑经过 y-x 这条边的点对数量
29 考虑y中选v个黑点 
30  v*(k-v)个点对
31 白点： (sz[y]-v)*(n-k-(sz[y]-v))
32 树上背包 
33 */ 
34 const int N=2002;
35 struct edge {
36     int nex,to,w;
37 }e[N<<1];
38 ll f[N][N];
39 int head[N],sz[N],cnt,n,m;
40 
41 void add_edge(int x,int y,int z) {
42     e[++cnt]=(edge){head[x],y,z}; head[x]=cnt;
43 }
44 
45 void dfs(int x,int ff) {
46     sz[x]=1; memset(f[x],-1,sizeof(f[x])); f[x][0]=0;
47     for(int i=head[x];i;i=e[i].nex) {
48         int y=e[i].to;
49         if(y==ff) continue;
50         dfs(y,x); sz[x]+=sz[y];
51     }
52     for(int i=head[x];i;i=e[i].nex) {
53         int y=e[i].to;
54         if(y==ff) continue;
55         for(int j=min(sz[x],m);j>=0;j--) {
56             for(int k=0;k<=min(sz[y],j);k++) {
57                 if(f[x][j-k]<0) continue;
58                 ll val=1ll*e[i].w*k*(m-k)+1ll*e[i].w*(sz[y]-k)*(n-m-(sz[y]-k));
59             //    cout<<val<<endl;
60                 f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]+val);
61             }
62         }
63     }
64 }
65 
66 int main() {
67     int x,y,z;
68     n=rd(); m=rd();
69     for(int i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add_edge(x,y,z),add_edge(y,x,z);
70     dfs(1,0);
71     printf("%lld",f[1][m]);
72 }

View Code

这篇关于一类经典的树形染色问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

一类经典的树形染色问题

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯