Strategic Game
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1760 Accepted Submission(s): 742
Problem Description
Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?
Your program should find the minimum number of soldiers that Bob has to put for a given tree.
The input file contains several data sets in text format. Each data set represents a tree with the following description:
the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)
The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.
For example for the tree:
the solution is one soldier ( at the node 1).
The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:
Sample Input
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)
Sample Output
典型的最小顶点覆盖!最小顶点覆盖 == 最大匹配(双向图)/2;
此题有个小细节,数据较大,要用邻接表,不然会超时!
连接:http://acm.hdu.edu.cn/showproblem.php?pid=1054
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
const int N = 1505;
int pre[N];
bool flag[N];
vector<int> map[N];
int n;
int find(int cur)
{
int i, k;
for(i = 0; i < map[cur].size(); i++)
{
k = map[cur][i];
if(!flag[k])
{
flag[k] = true;
if(pre[k] == -1 || find(pre[k]))
{
pre[k] = cur;
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, r, k, num, sum;
while(scanf("%d", &n) != EOF)
{
memset(pre, -1, sizeof(pre));
for(i = 0; i < n; i++) map[i].clear();
for(i = 0; i < n; i++)
{
scanf("%d:(%d)", &k, &num);
for(j = 0; j < num; j++)
{
scanf("%d", &r);
map[k].push_back(r); //用邻接表
map[r].push_back(k); //建双向图
}
}
sum = 0;
for(i = 0; i < n; i++)
{
memset(flag, false, sizeof(flag));
sum += find(i);
}
printf("%d\n", sum/2);
}
return 0;
}
- 大小: 661 Bytes
分享到:
相关推荐
hdu2215 最简单的最小圆覆盖
20. **Strategic Game (HDU 1054)** - **知识点**:最小点覆盖问题。 - **解题思路**:使用最大匹配算法找到最大匹配,然后利用Konig定理计算最小点覆盖。 21. **Swap (HDU 2819)** - **知识点**:行列匹配+...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
HDU1059的代码
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
对于特定问题,比如最大子序列和、最小覆盖子集等,需要掌握特定算法,如Kadane's algorithm或Dijkstra's algorithm。 四、数学基础:开启解题新维度 数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程...
hdu1001解题报告
hdu 1574 passed sorce
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论(模运算、最大公约数、最小公倍数)、组合数学(排列组合、容斥原理)、概率论等。 5. **贪心策略**:部分题目可以通过贪心算法求解,即每次做出...
HDU图论题目分类 HDU图论题目分类是指在杭州电子科技大学(Hangzhou Dianzi University)的判题平台HDU OJ(Online Judge)上收录的一系列图论题目的分类。本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本...
hdu2101AC代码
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。