題意：
? ? ? 給你一棵樹和m條邊，問(wèn)你在這些邊里面最多能夠挑出多少條邊，使得這些邊之間不能相互交叉。

思路：

? ? ?lca+貪心，首先對(duì)于給的每個(gè)條邊，我們用lca求出他們的公共節(jié)點(diǎn)，然后在公共節(jié)點(diǎn)的深度排序，排序之后我們先從最深的開始，每次判斷當(dāng)前的這條邊的兩點(diǎn)是否用過(guò)，如果沒(méi)用過(guò)，那么就把以當(dāng)前兩點(diǎn)的公共點(diǎn)為樹根的子樹全部標(biāo)記上，然后答案+1，就這樣一直遍歷到最后就行了，一開始敲了一個(gè)，TLE了，各種優(yōu)化之后還是TLE了，最后沒(méi)辦法了，用了一下自己存的一個(gè)LCA的模板，這個(gè)比我自己寫的LCA快，所以就AC了，思路就是貪心+LCA。

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm>#define MAXN 110000 #define MAXM 210000 using namespace std; //********************************************************* int n; struct EDGE {int v, next, w; }edge[MAXM]; int head[MAXN], e; int index, tmpdfn; int f[2 * MAXN], id[MAXN], vis[MAXN], pos[MAXN], dis[MAXN]; int mi[2 * MAXN][18]; void init() {memset(head, -1, sizeof(head));e = 0;index = tmpdfn = 0;memset(vis, 0, sizeof(vis));dis[1] = 0; } void add(int u, int v, int w) {edge[e].v = v;edge[e].w = w;edge[e].next = head[u];head[u] = e++; } void dfs(int u) {vis[u] = 1;int tmp = ++tmpdfn;f[++index] = tmp;id[tmp] = u;pos[u] = index;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!vis[v]){dis[v] = dis[u] + edge[i].w;dfs(v);f[++index] = tmp;}} } void rmqinit(int n, int *w) {for(int i = 1; i <= n; i++) mi[i][0] = w[i];int m = (int)(log(n * 1.0) / log(2.0));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){mi[j][i] = mi[j][i - 1];if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]);} } int rmqmin(int l,int r) {int m = (int)(log((r - l + 1) * 1.0) / log(2.0));return min(mi[l][m] , mi[r - (1 << m) + 1][m]); } int LCA(int l, int r) {if(pos[l] > pos[r]) swap(l, r);int ans = rmqmin(pos[l], pos[r]);return id[ans]; } //********************************************************** typedef struct {int a ,b ,ggdeep ,lca; }EDGEE;EDGEE edgee[110000];bool camp(EDGEE a ,EDGEE b) {return a.ggdeep > b.ggdeep; }int use[110000];void mk_dfs(int x) {use[x] = 1;for(int k = head[x] ;k + 1 ;k = edge[k].next){int to = edge[k].v;if(use[to] || dis[x] + 1 != dis[to]) continue;mk_dfs(to);} }int main() { int u, v, w, l, r ,m;while(~scanf("%d%d", &n, &m)){init();for(int i = 1 ;i < n ;i ++){scanf("%d %d" ,&u ,&v);add(u ,v ,1);add(v ,u ,1);}for(int i = 1 ;i <= m ;i ++)scanf("%d %d" ,&edgee[i].a ,&edgee[i].b);dfs(1);rmqinit(index, f);for(int i = 1 ;i <= m ;i ++){int lca = LCA(edgee[i].a ,edgee[i].b);edgee[i].ggdeep = dis[lca];edgee[i].lca = lca;}sort(edgee + 1 ,edgee + m + 1 ,camp);memset(use ,0 ,sizeof(use));int ans = 0;for(int i = 1 ;i <= m ;i ++){if(use[edgee[i].a] || use[edgee[i].b])continue;ans ++;mk_dfs(edgee[i].lca);}printf("%d\n" ,ans); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4912 LCA+贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。