宝马itms做课网站,用c 做网站,门户网站怎么建设,江门市骏业纸制品有限公司Description
Bob喜欢玩电脑游戏#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵#xff0c;使得这些士兵能了望到所有的路。
注意特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵使得这些士兵能了望到所有的路。
注意某个士兵在一个结点上时与该结点相连的所有边将都可以被了望到。
请你编一程序给定一树帮Bob计算出他需要放置最少的士兵.
Format
Input
第一行 N表示树中结点的数目。
第二行至第N1行每行描述每个结点信息依次为该结点标号ik(后面有k条边与结点I相连)。
接下来k个数分别是每条边的另一个结点标号r1r2…rk。
对于一个n(0n1500)个结点的树结点标号在0到n-1之间在输入数据中每条边只出现一次。
Output
输出文件仅包含一个数为所求的最少的士兵数目。
Samples
输入数据 1
4
0 1 1
1 2 2 3
2 0
3 0Copy
输出数据 1
1Copy
Hint 答案为1只要一个士兵在结点1上。 思路1:树形DP
可以先看看详解洛谷P1352 没有上司的舞会(树形DP经典例题)-CSDN博客
定义状态dp[x][0/1]表示x这个节点不放/放士兵
根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边 dp[x][0] dp[son][1] 其中son是u的子节点 如果当前节点放置士兵,只要将dp[x][1]加上它的子节点选不选的最小值就行了(因为树形dp自下而上,上面的节点不需要考虑)
dp[x][1]min(dp[son][0],dp[son][1]) 代码(树形DP)
#include bits/stdc.h
#define int long long
using namespace std;
int n,u,v,dp[10001][2];
vectorint vec[100001];
void dfs(int fa,int x)
{dp[x][1] 1;for(int i 0;i vec[x].size();i)if(vec[x][i] ! fa){dfs(x,vec[x][i]);dp[x][0] dp[vec[x][i]][1];dp[x][1] min(dp[vec[x][i]][0],dp[vec[x][i]][1]);}
}
signed main()
{cinn;for(int i 1;i n;i){int p;cinpu;for(int j 1;j u;j){cinv;vec[p].push_back(v);vec[v].push_back(p);}}dfs(-1,0);coutmin(dp[0][1],dp[0][0]);return 0;
} 思路2:贪心
可以按照反方向的深度优先遍历序列来进行贪心。每检查一个结点,如果当前点和当前点的父节点都不属于顶点覆盖集合,则将父节点加入到顶点覆盖集合,并标记当前节点和其父节点都被覆盖.
虽然说着思路很简单但是代码细节蛮多的可以参考一下。 代码(贪心)
#include bits/stdc.h
#define int long long
using namespace std;
int n,u,v,ans,fat[100001],cnt;
struct st
{int zhi,id;
}dp[100001];
bool vis[100001];
vectorint vec[100001];
void dfs(int fa,int x,int dep)
{dp[cnt] {dep,x};fat[x] fa;for(int i 0;i vec[x].size();i)if(vec[x][i] ! fa)dfs(x,vec[x][i],dep 1);
}
bool cmp(st x,st y)
{return x.zhi y.zhi;
}
signed main()
{cinn;for(int i 1;i n;i){int p;cinpu;for(int j 1;j u;j){cinv;vec[p].push_back(v);vec[v].push_back(p);}}vis[1501] 1;dfs(1501,0,1);sort(dp 1,1 dp n,cmp);for(int i 1;i n;i)if(vis[dp[i].id] 0 vis[fat[dp[i].id]] 0){vis[fat[dp[i].id]] 1;vis[dp[i].id] 1;ans;}coutans;return 0;
} 结语 如果这篇博客对您有帮助的话请点赞收藏关注支持一下呗!(o゜▽゜)o☆
