设为首页 加入收藏

TOP

hdu4912 Paths on the tree --- LCA贪心
2015-07-20 17:58:43 来源: 作者: 【大 中 小】 浏览:1次
Tags：hdu4912 Paths the tree --- LCA 贪心

给一棵n个结点的树，m条路径的起点和终点，

问至多可以选择多少条路径使其两两间没有公共点。


这题的主要问题是，

1、如何判断两条路径上没有交点

2、按什么策略来选

看上去感觉是最大匹配问题，但nm的范围较大问题1无法高效的解决。

画个图发现可能和LCA有关，但比赛时不知道这到底有什么用，完全没想贪心。

要选择尽量多，就是要尽量避免冲突。

我们选择一个点作为根，把给的边画出来建树就可以发现，尽量选深度大的路径可以使冲突尽量小。

于是把路径按LCA深度由大到小排序，依次和之前不冲突就可以选。

下面就是判断两条路径上有没有交点，

当一条路径选了之后，以其LCA的子树上的点为起点或终点的路径一定与其有交点。


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; const int maxn=1e5+10; int dep[maxn]; struct node { int v,id; node* next; }ed[maxn<<2],*head[maxn],*q[maxn]; struct qnode { int u,v,ans;//存询问结点，ans最近公共祖先 } qu[maxn]; bool cmp(const qnode &a,const qnode &b) { return dep[a.ans]>dep[b.ans]; } int fa[maxn],vis[maxn],cnt; void init(int n) { cnt=0; memset(vis,0,sizeof vis); memset(head,0,sizeof head); memset(q,0,sizeof q); for(int i=0;i<=n;i++) fa[i]=i; } int getfa(int x) { if(fa[x]==x) return x; return fa[x]=getfa(fa[x]); } void tarjan(int u) { fa[u]=u,vis[u]=1; for(node *p=q[u];p!=NULL;p=p->next) { if(vis[p->v]) { int id=p->id; qu[id].ans=getfa(p->v); } } for(node *p=head[u];p!=NULL;p=p->next) { if(!vis[p->v]) { tarjan(p->v); fa[p->v]=u; } } } void adde(node *e[],int u,int v,int id) { ed[cnt].v=v; ed[cnt].id=id; ed[cnt].next=e[u]; e[u]=&ed[cnt++]; } void dfs(int u) { for(node *p=head[u];p!=NULL;p=p->next) { if(dep[p->v]>dep[u]&&!vis[p->v]) { vis[p->v]=1; dfs(p->v); } } } void dfss(int u,int d) { for(node *p=head[u];p!=NULL;p=p->next) { if(!vis[p->v]) { vis[p->v]=1; dep[p->v]=d; dfss(p->v,d+1); } } } int main() { int n,m,i,a,b; while(~scanf("%d%d",&n,&m)) { init(n); for(i=0;i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu2377Bus Pass(较为复杂的建图+.. 下一篇：UVA11039- Building designing

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: