Strategic Game

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5034    Accepted Submission(s): 2297

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

1 2

Source

Recommend

``` 1 #include<cstring>
2 #include<cstdio>
3 #include<vector>
4 #include<iostream>
5 using namespace std;
6 const int maxn=1550;
7 vector<vector<int> >grid(maxn);
8 bool vis[maxn];
9 int savx[maxn];
10 int n;
11 int km(int x){
12     vector<int>::iterator it;
13   for(it=grid[x].begin();it<grid[x].end();it++){
14       if(!vis[*it]){
15            vis[*it]=1;
16       if(savx[*it]==-1||km(savx[*it])){
17         savx[*it]=x;
18         return 1;
19       }
20       }
21   }
22  return 0;
23 }
24
25 int main(){
26     int ans=0;
27     int a,b,c;
28     int km(int );
29     while(scanf("%d",&n)!=EOF){
30         ans=0;
31        memset(savx,-1,sizeof(savx));
32        for(int i=0;i<n;i++)
33           grid[i].clear();
34       for(int i=0;i<n;i++){
35            scanf("%d:(%d)",&a,&b);
36           for(int j=0;j<b;j++){
37          scanf("%d",&c);
38          grid[a].push_back(c);
39          grid[c].push_back(a);
40           }
41       }
42      for(int i=0;i<n;i++){
43        memset(vis,0,sizeof(vis));
44        ans+=km(i);
45      }
46     printf("%d\n",ans/2);
47     }
48  return 0;
49 }```

0 条评论

• 排序一栏（总结帖）

学了很多的排序，基数排序，堆排序，希尔排序，选择排序，归并排序，快速排序，冒泡排序.....等等，尽管网上好文，如堆山之牛毛，但是还是没有自己写，来...

• Flyod 算法(两两之间的最短路径)

Flyod 算法(两两之间的最短路径) 动态规划方法，通过相邻矩阵， 然后把最后的结果存在这么一个矩阵里面，(i,j), #include <iostream...

• 【PAT甲级】1002 A+B for Polynomials (25分)

This time, you are supposed to find A+B where A and B are two polynomials.

• 暑假（补）-4

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 动态规划算法的基本思想与分治法类似，也是将待求解的问题...

• 约瑟夫问题（c++实现）

描述：约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就...

• Day5上午解题报告

预计分数：100+40+30=170 实际假分数：0+0+0=0 CE*3 实际真分数：60+50+0=110 老师没把我的程序放的文件夹里面，于是。。。。。 ...

• 挖掘机技术哪家强（c++实现）

描述：为了用事实说明挖掘机技术到底哪家强，组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

• 「CodeForces - 598B」Queries on a String

字符串s（1 ≤ |s| ≤ 10 000），有m（1 ≤ m ≤ 300）次操作，每次给l,r,k，代表将r位置插入l位置前，执行k（1 ≤ k ≤ 1 00...

• 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...