国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > HDU 4912 LCA+策略

HDU 4912 LCA+策略

来源:程序员人生   发布时间:2016-08-03 09:18:19 阅读次数:980次

点击打开链接

题意:给了1个树,然后m条路径,问最多可以选多少条路径而没有1个点是重复使用的,如第2组样例,3条路径是4—2—5和6—3—7和2—1—3,那末只能选前两个使得所选路径最多

思路:没啥思路,看了正解居然是LCA+贪心,好嘛可以这样斟酌,对所有的可选路径,我们先选择最下面的对上面是没有影响的,那末我们可以对每条路经的最上面的那个点进行排序,就按深度由大到小排序,然后这个最上面的点不就是LCA嘛,然后由于是由下到上的,那末对每次以后就要将以LCA为根的子树节点全部标记,由于它作为深度最深的点以后它的下面在出现肯定是不符合的了       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; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生