HDU 4912 LCA+策略
來源：程序員人生 發(fā)布時間：2016-08-03 09:18:19 閱讀次數(shù)：2460次
點擊打開鏈接
題意：給了1個樹，然后m條路徑，問最多可以選多少條路徑而沒有1個點是重復使用的，如第2組樣例，3條路徑是4—2—5和6—3—7和2—1—3，那末只能選前兩個使得所選路徑最多
思路：沒啥思路，看了正解居然是LCA+貪心，好嘛可以這樣斟酌，對所有的可選路徑，我們先選擇最下面的對上面是沒有影響的，那末我們可以對每條路經(jīng)的最上面的那個點進行排序，就按深度由大到小排序，然后這個最上面的點不就是LCA嘛，然后由于是由下到上的，那末對每次以后就要將以LCA為根的子樹節(jié)點全部標記，由于它作為深度最深的點以后它的下面在出現(xiàn)肯定是不符合的了 PS：主要是不敢去想用貪心，自己就是想固然的寫根本不知道這么貪心對不對（弱哭）
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=100010;
bool vis[maxn];
int L[maxn*2],E[maxn*2],H[maxn],dis[maxn],dp[2*maxn][20],num[maxn],head[maxn],kkk,pre[maxn];
struct node{
int to,next;
}EE[maxn*10];
void add_edge(int u,int v){
EE[kkk].to=v;EE[kkk].next=head[u];head[u]=kkk++;
}
int k,n;
void dfs(int t,int deep){
k++;E[k]=t;L[k]=deep;H[t]=k;
for(int i=head[t];i!=⑴;i=EE[i].next){
int tt=EE[i].to;
if(!vis[tt]){
vis[tt]=1;pre[tt]=t;
dfs(tt,deep+1);
k++;E[k]=t;L[k]=deep;
}
}
}
void RMQ_init(){
for(int i=1;i<=2*n⑴;i++) dp[i][0]=i;
for(int i=1;(1<<i)<=2*n⑴;i++){
for(int j=1;j+(1<<i)⑴<=2*n⑴;j++){
if(L[dp[j][i⑴]]<L[dp[j+(1<<(i⑴))][i⑴]]) dp[j][i]=dp[j][i⑴];
else dp[j][i]=dp[j+(1<<(i⑴))][i⑴];
}
}
}
int RMQ(int le,int ri){
le=H[le];ri=H[ri];
if(le>ri) swap(le,ri);
int kk=0;
while((1<<(kk+1))<=ri-le+1) kk++;
if(L[dp[le][kk]]<L[dp[ri-(1<<kk)+1][kk]]) return E[dp[le][kk]];
else return E[dp[ri-(1<<kk)+1][kk]];
}
struct edge{
int f,x,y;
}tmp[maxn];
bool cmp(const edge &a,const edge &b){
return L[H[a.f]]>L[H[b.f]];
}
void visdfs(int x){
vis[x]=1;
for(int i=head[x];i!=⑴;i=EE[i].next){
int t=EE[i].to;
if(t==pre[x]||vis[t]) continue;
visdfs(t);
}
}
int main(){
int q,u,v;
while(scanf("%d%d",&n,&q)!=⑴){
for(int i=0;i<=n;i++) vis[i]=0;
memset(head,⑴,sizeof(head));
for(int i=0;i<n⑴;i++){
scanf("%d%d",&u,&v);
add_edge(u,v);add_edge(v,u);
}
kkk=0;k=0;vis[1]=1;dfs(1,1);RMQ_init();
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
int en=RMQ(u,v);
tmp[i].f=en;tmp[i].x=u;tmp[i].y=v;
}
int ans=0;
for(int i=1;i<=n;i++) vis[i]=0;
sort(tmp+1,tmp+1+q,cmp);
for(int i=1;i<=q;i++){
if(vis[tmp[i].x]==0&&vis[tmp[i].y]==0){
ans++;
int uu=tmp[i].x,vv=tmp[i].y,ff=tmp[i].f;
visdfs(ff);
}
}
printf("%d\n",ans);
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
