首页 > 代码库 > hdu--4912--终于解脱了
hdu--4912--终于解脱了
....历经n发wa之后 终于解脱了
这感觉....无法言表...
其实 这题你说难吧？ 对于我而言 一共就做过一道lca的人来说 是有点难的
可是吧 当你慢慢地写下来 其实代码那么长 又不怎么难
对于此题 就是先求出query中2个结点的lca之后 然后dfs它们的lca 根据深度进行排序
这个其实不难理解吧？ 当然深度越大的 就是离根结点越远 首先进行搜索
然后 就是每搜到一个点 就将它进行标记-已访问过
深搜的时候 注意下 不仅要判断是否访问过 而且要判断这2点的深度关系 肯定是从小的搜到大的
最最注意的就是
depth[v] = depth[u] + 1这句话 不要太随意地写在了lca_tarjan(v)的后面
表示 我就一不留神 写错了 找了好久。。
其余的 就是可以再去好好思索下lca_tarjan的整个算法实现过程
准备 可能 晚上再去学校lca的在线算法...
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int Ncnt , Qcnt; 7 const int size = 100010; 8 struct data 9 { 10 int id; 11 int from; 12 int to; 13 int next; 14 int lca; 15 }; 16 data node[size*2]; 17 int Nhead[size]; 18 data query[size*2]; 19 data graph[size]; 20 int Qhead[size]; 21 bool vis[size]; 22 int father[size]; 23 int depth[size]; 24 bool check[size]; 25 26 bool cmp( data p , data q ) 27 { 28 return depth[p.lca] > depth[q.lca]; 29 } 30 31 void init( ) 32 { 33 memset( Nhead , -1 , sizeof(Nhead) ); 34 memset( Qhead , -1 , sizeof(Qhead) ); 35 memset( vis , false , sizeof(vis) ); 36 memset( check , false , sizeof(check) ); 37 depth[1] = 0; 38 } 39 40 int find( int x ) 41 { 42 return x == father[x] ? x : father[x] = find( father[x] ); 43 } 44 45 void addNedge( int st , int end ) 46 { 47 node[Ncnt].to = end; 48 node[Ncnt].next = Nhead[st]; 49 Nhead[st] = Ncnt ++; 50 } 51 52 void addQedge( int id , int st , int end ) 53 { 54 query[Qcnt].id = id; 55 query[Qcnt].from = st; 56 query[Qcnt].to = end; 57 query[Qcnt].next = Qhead[st]; 58 Qhead[st] = Qcnt ++; 59 } 60 61 void lca_tarjan( int u ) 62 { 63 int v; 64 father[u] = u; 65 vis[u] = true; 66 for( int i = Nhead[u] ; ~i ; i = node[i].next ) 67 { 68 v = node[i].to; 69 if( !vis[v] ) 70 { 71 depth[v] = depth[u] + 1; 72 lca_tarjan( v ); 73 father[v] = u; 74 } 75 } 76 for( int i = Qhead[u] ; ~i ; i = query[i].next ) 77 { 78 v = query[i].to; 79 if( vis[v] ) 80 { 81 graph[ query[i].id ].lca = find(v); 82 } 83 } 84 } 85 86 void dfs( int u ) 87 { 88 int v; 89 check[u] = true; 90 for( int i = Nhead[u] ; ~i ; i = node[i].next ) 91 { 92 v = node[i].to; 93 if( !check[v] && depth[u]<depth[v] ) 94 dfs(v); 95 } 96 } 97 98 int main() 99 {100 cin.sync_with_stdio(false);101 int n , m , st , end , lca , ans , temp;102 while( cin >> n >> m )103 {104 ans = Ncnt = Qcnt = 0;105 init( );106 for( int i = 0 ; i<n-1 ; i++ )107 {108 cin >> st >> end;109 addNedge( st , end );110 addNedge( end , st );111 }112 for( int i = 0 ; i<m ; i++ )113 {114 cin >> st >> end;115 addQedge( i , st , end );116 addQedge( i , end , st );117 graph[i].from = st;118 graph[i].to = end;119 }120 lca_tarjan(1);121 sort( graph , graph+m , cmp );122 for( int i = 0 ; i<m ; i++ )123 {124 st = graph[i].from;125 end = graph[i].to;126 lca = graph[i].lca;127 if( !check[st] && !check[end] )128 {129 ans ++;130 dfs( lca );131 }132 }133 cout << ans << endl;134 }135 return 0;136 }
today:
关于思念你的这件小事
躲得过对酒当歌的夜晚
躲不过四下无人的街道
hdu--4912--终于解脱了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。