首页 > 代码库 > HDU 4912 lca贪心
HDU 4912 lca贪心
Paths on the tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 297 Accepted Submission(s): 93
Problem Description
bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.
There are m paths on the tree. bobo would like to pick some paths while any two paths do not share common vertices.
Find the maximum number of paths bobo can pick.
There are m paths on the tree. bobo would like to pick some paths while any two paths do not share common vertices.
Find the maximum number of paths bobo can pick.
Input
The input consists of several tests. For each tests:
The first line contains n,m (1≤n,m≤105). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following m lines contain 2 integers ui,vi denoting a path between vertices ui and vi (1≤ui,vi≤n).
The first line contains n,m (1≤n,m≤105). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following m lines contain 2 integers ui,vi denoting a path between vertices ui and vi (1≤ui,vi≤n).
Output
For each tests:
A single integer, the maximum number of paths.
A single integer, the maximum number of paths.
Sample Input
3 2 1 2 1 3 1 2 1 3 7 3 1 2 1 3 2 4 2 5 3 6 3 7 2 3 4 5 6 7
Sample Output
1 2
Author
Xiaoxu Guo (ftiasch)
一棵树,给出m条路径,然后问最多选择多少条路径,使得每两条路径之间没有 任何公共点,公共边。
把m条路径求出lca,然后按照lca深度从大到小排序,把路径上经过的点标记出来,贪心即可。
代码:
#include <stdio.h> #include <iostream> #include <algorithm> #include <sstream> #include <stdlib.h> #include <string.h> #include <limits.h> #include <string> #include <time.h> #include <math.h> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const int maxn=100010; int head[maxn],tol,fa[maxn][20],dep[maxn]; struct Edge{ int next,to; Edge(int _next=0,int _to=0){ next=_next;to=_to; } }edge[10*maxn]; void addedge(int u,int v){ edge[tol]=Edge(head[u],v); head[u]=tol++; } void bfs(int s){ queue<int> q; dep[s]=0,fa[s][0]=s; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[u][0])continue; fa[v][0]=u; dep[v]=dep[u]+1; q.push(v); } } } int LCA(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=19;i>=0;i--)if((1<<i)&(dep[x]-dep[y]))x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } struct QQ{ int u,v,lca; }pp[100100]; bool vis[100100]; int n,m; bool cmp(QQ a,QQ b){ return dep[a.lca]>dep[b.lca]; } int main() { while(~scanf("%d%d",&n,&m)){ memset(head,-1,sizeof(head)); tol=0; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } bfs(1); for(int i=0;i<m;i++){ scanf("%d%d",&pp[i].u,&pp[i].v); pp[i].lca=LCA(pp[i].u,pp[i].v); } sort(pp,pp+m,cmp); memset(vis,0,sizeof(vis)); int ans=0; for(int i=0;i<m;i++){ int lca=pp[i].lca,flag=1,u=pp[i].u,v=pp[i].v; if(vis[u]||vis[v]||vis[lca])continue; for(int j=u;j!=lca;j=fa[j][0]) if(vis[j]){ flag=0;break; } for(int j=v;j!=lca;j=fa[j][0]) if(vis[j]){ flag=0;break; } if(!flag)continue; ans++; vis[lca]=1; for(int j=u;j!=lca;j=fa[j][0])vis[j]=1; for(int j=v;j!=lca;j=fa[j][0])vis[j]=1; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。