首页 > 代码库 > HDU 4912 Paths on the tree

HDU 4912 Paths on the tree

2024-07-16 05:42:43   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4912

题意：给一棵树，再给一些路径，求最多有多少条路径不相交。

题解：主要是贪心的想法。用LCA处理出路径的层数，然后从最深处的节点往上找。因为节点越深，对其他路径影响度越小，相交的可能性越低。需要手动扩栈。

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 #include <iostream>  3 #include <cstring>  4 #include <cstdio>  5 #include <cstdlib>  6 #include <cmath>  7 #include <string>  8 #include <vector>  9 #include <list> 10 #include <map> 11 #include <queue> 12 #include <stack> 13 #include <bitset> 14 #include <algorithm> 15 #include <numeric> 16 #include <functional> 17 #include <set> 18 #include <fstream> 19  20 using namespace std; 21  22 const int INF=0xfffffff; 23 const int maxn=100010; 24  25 struct edge 26 { 27     int v,next; 28 }G[maxn*2]; 29 struct node 30 { 31     int u,v,id; 32 }es[maxn]; 33 int head[maxn],idx; 34 int LCA[maxn],par[maxn],d[maxn]; 35 bool used[maxn]; 36 int parent[maxn]; 37 int depth[maxn]; 38 vector<pair<int,int> >query[maxn]; 39  40 int find(int x) 41 { 42     return x==par[x]?x:par[x]=find(par[x]); 43 } 44  45 void build(int u,int v) 46 { 47     G[idx].v=v; 48     G[idx].next=head[u]; 49     head[u]=idx++; 50 } 51  52 void add_edge(int u,int v) 53 { 54     build(u,v); 55     build(v,u); 56 } 57  58 void dfs(int u,int root) 59 { 60     par[u]=u; 61     pair<int,int>PI; 62     for(int i=0;i<(int)query[u].size();i++) 63     { 64         PI=query[u][i]; 65         if(d[PI.first]==-1) continue; 66         LCA[PI.second]=find(PI.first); 67     } 68     for(int k=head[u];k!=-1;k=G[k].next) 69     { 70         int v=G[k].v; 71         if(v==root) continue; 72         d[v]=d[u]+1; 73         dfs(v,u); 74         par[v]=u; 75     } 76 } 77  78 bool cmp(node& a,node& b) 79 { 80     int u=LCA[a.id]; 81     int v=LCA[b.id]; 82     return d[u]>d[v]; 83 } 84  85 void init(int n) 86 { 87     memset(used,0,sizeof(used)); 88     memset(head,-1,sizeof(head)); 89     idx=0; 90     memset(d,-1,sizeof(d)); 91     for(int i=0;i<=n;i++) query[i].clear(); 92 } 93  94 void dfs_res(int u) 95 { 96     used[u]=true; 97     for(int k=head[u];k!=-1;k=G[k].next) 98     { 99         int v=G[k].v;100         if(used[v]||d[v]<d[u]) continue;101         dfs_res(v);102     }103 }104 105 int main()106 {107     //freopen("/Users/apple/Desktop/暑假/30/30/in","r",stdin);108     int N,M;109     while(scanf("%d%d",&N,&M)!=EOF)110     {111         init(N);112         for(int i=1;i<N;i++)113         {114             int u,v;115             scanf("%d%d",&u,&v);116             add_edge(u,v);117         }118         for(int i=0;i<M;i++)119         {120             int u,v;121             scanf("%d%d",&u,&v);122             query[u].push_back(make_pair(v,i));123             query[v].push_back(make_pair(u,i));124             es[i].u=u;125             es[i].v=v;126             es[i].id=i;127         }128         d[1]=0;129         dfs(1,-1);130         sort(es,es+M,cmp);131         int res=0;132         for(int i=0;i<M;i++)133         {134             if(!used[es[i].u]&&!used[es[i].v])135             {136                 res++;137                 dfs_res(LCA[es[i].id]);138             }139         }140         printf("%d\n",res);141     }142     return 0;143 }

 


联系
我们