首页 > 代码库 > HDU 2586 + HDU 4912 最近公共祖先
HDU 2586 + HDU 4912 最近公共祖先
先给个LCA模板
HDU 1330(LCA模板)
#include <cstdio>#include <cstring>#define N 40005struct Edge{ int x,y,d,ne;};Edge e[N*2],e2[N*2];int be[N],be2[N],all,all2,n,m;bool vis[N];int fa[N];int ancestor[N][3];int dis[N];void add(int x, int y, int d, Edge e[], int be[], int &all){ e[all].y=y;e[all].x=x;e[all].d=d; e[all].ne=be[x]; be[x]=all++; e[all].y=x;e[all].x=y;e[all].d=d; e[all].ne=be[y]; be[y]=all++;}void init(){ all=all2=0; memset(be,-1,sizeof(be)); memset(be2,-1,sizeof(be2)); memset(vis,0,sizeof(vis)); for(int i=0; i<=n; i++) fa[i]=i;}int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x];}void tarjan(int u){ vis[u]=1; for(int i=be2[u]; i!=-1; i=e2[i].ne) if(vis[e2[i].y]) ancestor[e2[i].d][2]=find(e2[i].y); for(int i=be[u]; i!=-1; i=e[i].ne) if(!vis[e[i].y]) { dis[e[i].y]=dis[u]+e[i].d; tarjan(e[i].y); fa[e[i].y]=u; }}int main(){ int tt; scanf("%d",&tt); while(tt--) { int x,y,d; scanf("%d%d",&n,&m); init(); for(int i=0; i<n-1; i++) { scanf("%d%d%d",&x,&y,&d); add(x,y,d,e,be,all); } for(int i=0; i<m; i++) { scanf("%d%d",&x,&y); add(x,y,i,e2,be2,all2); ancestor[i][0]=x; ancestor[i][1]=y; } dis[1]=0; tarjan(1);//从根节点开始 for(int i=0; i<m; i++) printf("%d\n",dis[ancestor[i][0]]+dis[ancestor[i][1]]-2*dis[ancestor[i][2]]); } return 0;}
HDU 4912
Paths on the tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 428 Accepted Submission(s): 128
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 21 21 31 21 37 31 21 32 42 53 63 72 34 56 7
Sample Output
12
贪心法，找出给定路径左右节点的最近公共祖先，按其最近公共祖先的深度从大到小插入，每次插入将其子树标记，之后若路径节点若已访问则判不可行，否则ans+1
#include <iostream>#include <cstring>#include <cstdio>#include <vector>#define max(x,y) ((x)>(y)?(x):(y))#define NN 200002 // number of houseusing namespace std;int be[NN],all,ans;bool vis2[NN],vis3[NN];typedef struct node{ int v; int d; struct node *nxt;}NODE;struct edge{ int u,v,ne;}e[NN];NODE *Link1[NN];NODE edg1[NN * 2]; NODE *Link2[NN];NODE edg2[NN * 2]; int idx1, idx2, N, M;int res[NN][3]; int fat[NN];int vis[NN];int dis[NN];void Add(int u, int v, int d, NODE edg[], NODE *Link[], int &idx){ edg[idx].v = v; edg[idx].d = d; edg[idx].nxt = Link[u]; Link[u] = edg + idx++; edg[idx].v = u; edg[idx].d = d; edg[idx].nxt = Link[v]; Link[v] = edg + idx++;}int find(int x){ if(x != fat[x]){ return fat[x] = find(fat[x]); } return x;}void Tarjan(int u){ vis[u] = 1; fat[u] = u; for (NODE *p = Link2[u]; p; p = p->nxt){ if(vis[p->v]){ res[p->d][2] = find(p->v); } } for (NODE *p = Link1[u]; p; p = p->nxt){ if(!vis[p->v]){ dis[p->v] = dis[u] + p->d; Tarjan(p->v); fat[p->v] = u; } }}void add(int fa,int x,int y){ ++all; e[all].u=x; e[all].v=y; e[all].ne=be[fa]; be[fa]=all;}void color(int u){ for (NODE *p = Link1[u]; p; p = p->nxt) if(vis3[p->v] && !vis2[p->v]) { vis2[p->v]=1; color(p->v); }}void dfs(int u){ vis[u]=1; for (NODE *p = Link1[u]; p; p = p->nxt) if(!vis[p->v]) dfs(p->v); for (int i=be[u]; i!=-1; i=e[i].ne) if(!vis2[e[i].u] && !vis2[e[i].v]) { vis2[u]=1; ans++; color(u); } vis3[u]=1;}int main() { int T, i, u, v, d; while(scanf("%d%d", &N, &M)!=EOF) { idx1 = 0; memset(Link1, 0, sizeof(Link1)); for (i = 1; i < N; i++){ scanf("%d%d", &u, &v); d=0; Add(u, v, d, edg1, Link1, idx1); } idx2 = 0; memset(Link2, 0, sizeof(Link2)); for (i = 1; i <= M; i++){ scanf("%d%d", &u, &v); Add(u, v, i, edg2, Link2, idx2); res[i][0] = u; res[i][1] = v; } memset(vis, 0, sizeof(vis)); dis[1] = 0; Tarjan(1); all=0; memset(be,-1,sizeof(be)); memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); memset(vis3,0,sizeof(vis3)); for(int i=1;i<=M; i++) add(res[i][2],res[i][0],res[i][1]); for(int i=1; i<=N; i++) fat[i]=i; ans=0; dfs(1); printf("%d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。