文登住房与建设局网站,开网店货源怎么弄,开源展示型网站,wordpress网站修改域名题干#xff1a; 谷同学很喜欢玩计算机游戏#xff0c;特别是战略游戏#xff0c;但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题#xff1a;他必须在一个中世纪的城堡里设防#xff0c;城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以… 题干 谷同学很喜欢玩计算机游戏特别是战略游戏但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题他必须在一个中世纪的城堡里设防城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗 你的任务是给出士兵的最少数目。 输入包含多组数据。每组数据表示一棵树在每组数据中 第一行是结点的数目。 接下来的几行每行按如下格式描述一个结点结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 ...... 结点标识符道路的数目 或者 结点标识符 : (0) 对于 n (0n1500) 个结点结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。 对于每组数据各给出一个整数表示士兵的最少数目。
测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 4↵0:(1) 1↵1:(2) 2 3↵2:(0)↵3:(0)↵5↵3:(3) 1 4 2↵1:(1) 0↵2:(0)↵0:(0)↵4:(0)↵以文本方式显示 1↵2↵1秒64M0 代码如下 这里和小学期的知识对应起来了。动态规划dp[n][2]的设计
#include iostream
#include cstring
using namespace std;const int MAXN 1505;
int dp[MAXN][2], visited[MAXN], link[MAXN][MAXN];
void DFS(int root)
{visited[root] 1;for (int i 0; link[root][i] ! -1; i){int m link[root][i];if (!visited[m]){DFS(m);dp[root][1] dp[m][0];dp[root][0] min(dp[m][0], dp[m][1]);}}dp[root][0];
}
int main()
{int n;while (scanf(%d, n) ! EOF){memset(dp, 0, sizeof(dp));memset(visited, 0, sizeof(visited));memset(link, 0, sizeof(link));int node, next, temp, root;for (int i 0; i n; i){scanf(%d:(%d), node, next);root (!i) ? node : root;int j 0;for (; j next; j){cin temp;link[node][j] temp;}link[node][j] -1;}DFS(root);cout min(dp[root][0], dp[root][1]) endl;}return 0;
}
