做的比较好的网站推荐,广东新闻频道直播在线观看高清,怎样查看一个网站是用什么开源程序做的,网站导航栏图标P2016 战略游戏 时间限制 1.00s 内存限制 125.00MB
题目描述 Bob喜欢玩电脑游戏#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵#x…P2016 战略游戏 时间限制 1.00s 内存限制 125.00MB
题目描述 Bob喜欢玩电脑游戏特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵使得这些士兵能了望到所有的路。
注意某个士兵在一个结点上时与该结点相连的所有边将都可以被了望到。
请你编一程序给定一树帮Bob计算出他需要放置最少的士兵.
输入格式 第一行 N表示树中结点的数目。
第二行至第N1行每行描述每个结点信息依次为该结点标号ik(后面有k条边与结点I相连)。
接下来k个数分别是每条边的另一个结点标号r1r2…rk。
对于一个n(0n1500)个结点的树结点标号在0到n-1之间在输入数据中每条边只出现一次。
输出格式 输出文件仅包含一个数为所求的最少的士兵数目。
例如对于如下图所示的树 01 2 3 答案为1只要一个士兵在结点1上。
输入输出样例 输入 #1 复制 4 0 1 1 1 2 2 3 2 0 3 0 输出 #1 复制 1
解题思路 用dp[u][1]dp[u][1]dp[u][1]来代表在uuu节点上放士兵所需要的最少士兵数 而dp[u][0]dp[u][0]dp[u][0]代表不在uuu节点上放士兵所需要的最少士兵数 我们可知若在uuu节点上放士兵则 dp[u][1]dp[u][1]min(dp[v][1],dp[v][0])dp[u][1]dp[u][1]min(dp[v][1],dp[v][0])dp[u][1]dp[u][1]min(dp[v][1],dp[v][0]) 若不在uuu节点放士兵则其子节点一定需全部放士兵因此 dp[u][0]dp[u][0]dp[v][1]dp[u][0]dp[u][0]dp[v][1]dp[u][0]dp[u][0]dp[v][1]
代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
vectorint m[1600];
int dp[1600][2];
int N;
bool vis[1600];
void dfs(int s,int fa) {dp[s][1]1;dp[s][0]0;for(int i0;im[s].size();i) {if(m[s][i]fa) continue;dfs(m[s][i],s);dp[s][1]min(dp[m[s][i]][0],dp[m[s][i]][1]);dp[s][0]dp[m[s][i]][1];}return;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);#endif//freopen(out.txt, w, stdout);//ios::sync_with_stdio(0),cin.tie(0);scanf(%d,N);rep(i,1,N) {int a,b,c;scanf(%d %d,a,b);rep(j,1,b) {scanf(%d,c);m[a].push_back(c);}}dfs(0,-1);printf(%d\n,min(dp[0][1],dp[0][0]));return 0;
}
