专栏首页mlhdu---(1054)Strategic Game(最小覆盖边)

hdu---(1054)Strategic Game(最小覆盖边)

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

Southeastern Europe 2000

Recommend

代码:  这里是最少覆盖边,开始一直搞最小覆盖点,然后各种不得劲,.....后面看了以下提示,然后就明白了。但是改了之后有开始tie,没办法,只能最后用起了邻接表(我用 的是vector来替代的)  最小覆盖点 =顶点数- 最大匹配数  、  最小覆盖边= 等于(无向图)最大匹配/2;

代码:

 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 条评论
登录 后参与评论

相关文章

  • 排序一栏(总结帖)

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

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

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

    Gxjun
  • 多线程处理N维度topk问题demo--[c++]

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

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

    韩旭051
  • 暑假(补)-4

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

    AngelNH
  • 约瑟夫问题(c++实现)

    描述:约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1 开始报数。就...

    用户2038589
  • Day5上午解题报告

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

    attack
  • 挖掘机技术哪家强(c++实现)

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

    用户2038589
  • 「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种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券