首页 > 代码库 > LA 2038 最少点覆盖
LA 2038 最少点覆盖
题目链接：https://vjudge.net/problem/UVALive-2038
题意：我看了原题，lrj的书上题意写错了，应该是最少点覆盖，当然可以用最大匹配去做，由于是树形的；
可以树形DP；
d[u][0] : u 结点 不放；
d[u][1] : u 结点放；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1500 + 5; 6 int n; 7 vector<int> G[maxn]; 8 9 int d[maxn][2];10 int p[maxn];11 12 int dfs(int u,int fa) {13 int d = G[u].size();14 for(int i=0;i<d;i++)15 {16 int v = G[u][i];17 if(v!=fa)18 dfs(v,p[v]=u);19 }20 }21 22 int dp(int cur,int f,int pa) {23 if(d[cur][f]>0)24 return d[cur][f];25 if(f==1) {26 d[cur][f] = 1;27 for(int i=0;i<G[cur].size();i++) {28 int v = G[cur][i];29 if(v!=pa)30 d[cur][f] +=min(dp(v,0,cur),dp(v,1,cur));31 }32 }33 else {34 for(int i=0;i<G[cur].size();i++) {35 int v = G[cur][i];36 if(v!=pa)37 d[cur][f] +=dp(v,1,cur);38 }39 }40 return d[cur][f];41 }42 43 44 int main()45 {46 while(scanf("%d",&n)!=EOF) {47 48 memset(d,0,sizeof(d));49 for(int i=0;i<n;i++)50 G[i].clear();51 int u,v,num;52 for(int i=0;i<n;i++) {53 scanf("%d:(%d)",&u,&num);54 for(int j=0;j<num;j++) {55 scanf("%d",&v);56 G[u].push_back(v);57 G[v].push_back(u);58 }59 }60 61 p[0] = -1;62 dfs(0,-1);63 printf("%d\n",min(dp(0,0,-1),dp(0,1,-1)));64 65 }66 return 0;67 }
LA 2038 最少点覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。