hdu 4582 (树上的贪心)-白红宇

hdu 4582 (树上的贪心)

阅读量：6679 次

发布时间：2019-06-25

本文共 1668 字，大约阅读时间需要 5 分钟。

题意：一张无向图中告诉你一个dfs树，还有若干反向边。问你如何选取最小的边使得所有只包含一条反向边的环被覆盖。

思路：我们把有反向边的点与反向边连接的点在树上的路径称作一个区间，可以想到了从叶子结点开始向上到一个区间到不得不选边覆盖的时候在选边，同样能选的边越靠近根节点越好。关键是在程序实现上，自己实现的时候用的是vector<bool>来标记边的状态果断超时，网上搜到一种用bitset，以前从来没用过太神了，代码又短思路又清晰参考http://hi.baidu.com/zjut_dd/item/5d3543e55ba0ebebe0a5d4d7

主要就是从低至上每次遇到反向边则记录，若是当前节点到其父亲结点必须选了则选上（选上了则代表当前子树的所有结点连接的反向边全部搞定了），否则的话则向上一层传递还未选择的区间。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-05-13 22:22 5  * Filename     : hdu_4582.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 2010;34 vector
                      
                        Map1[LEN], Map2[LEN];35 int vex[LEN][1010];36 int n, m, vis[LEN], ans;37 38 void setvex(int pa, int pb){39 int tn = pb/30;40 vex[pa][tn] |= (1<<(pb%30));41 }42 43 bool getvex(int pa, int pb){44 int tn = pb/30;45 if(vex[pa][tn] & (1<<(pb%30))) return true;46 return false;47 }48 49 void dfs(int v, int fa){50 vis[v] = 1;51 memset(vex[v], 0, sizeof vex[v]);52 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3728244.html

你可能感兴趣的文章