频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 3728 tarjan+带权路径并查集
2012-07-08 16:40:00           
收藏   我要投稿
[cpp]
#include<iostream> 
#include<cstdio> 
#include<vector> 
using namespace std; 
const int N=55009; 
int n,q,a,b,fa[N],vis[N],ans[N],v[N],Max[N],Min[N],up[N],down[N]; 
vector<int> need[N],edge[N],kv[N]; 
int find(int x) 

    if(x==fa[x])return x; 
    int y=fa[x]; 
    fa[x]=find(fa[x]); 
 
    up[x]=max(Max[y]-Min[x],max(up[x],up[y])); 
    down[x]=max(Max[x]-Min[y],max(down[x],down[y])); 
 
    Max[x]=max(Max[y],Max[x]); 
    Min[x]=min(Min[y],Min[x]); 
 
    return fa[x]; 

 
void tarjan(int x) 

    vis[x]=1; 
    for(int i=0;i<need[x].size();i=i+2) 
    { 
        int y=need[x][i]; 
        if(vis[y]) 
        { 
            int t=find(y),f=need[x][i+1]; 
            if(f>0) 
            { 
                kv[t].push_back(x); 
                kv[t].push_back(y); 
            } 
            else 
            { 
                kv[t].push_back(y); 
                kv[t].push_back(x); 
            } 
            kv[t].push_back(f>0?f:-f); 
        } 
    } 
    for(int i=0;i<edge[x].size();i++) 
    { 
        int y=edge[x][i]; 
        if(!vis[y]) 
        { 
            tarjan(y); 
            fa[y]=x; 
        } 
    } 
    for(int i=0;i<kv[x].size();i=i+3) 
    { 
        int a=kv[x][i],b=kv[x][i+1],f=kv[x][i+2]; 
        find(a);find(b); 
        ans[f]=max(up[a],max(down[b],Max[b]-Min[a])); 
    } 

void init() 

    for(int i=0;i<=n;i++) 
    { 
        fa[i]=i; 
        vis[i]=0; 
        need[i].clear(); 
        edge[i].clear(); 
        kv[i].clear(); 
    } 
    for(int i=1;i<=n;i++) 
    { 
        scanf("%d",&v[i]); 
        Max[i]=v[i]; 
        Min[i]=v[i]; 
        up[i]=0; 
        down[i]=0; 
    } 
    for(int i=0;i<n-1;i++) 
    { 
        scanf("%d%d",&a,&b); 
        edge[a].push_back(b); 
        edge[b].push_back(a); 
    } 
    scanf("%d",&q); 
    for(int i=1;i<=q;i++) 
    { 
        scanf("%d%d",&a,&b); 
        need[a].push_back(b); 
        need[a].push_back(i); 
        need[b].push_back(a); 
        need[b].push_back(-i); 
    } 
    tarjan(1);   www.2cto.com
    for(int i=1;i<=q;i++) 
    { 
        printf("%d\n",ans[i]); 
    } 

int main() 

    while(scanf("%d",&n)!=EOF) 
    { 
        init(); 
    } 

作者:wsniyufang
点击复制链接 与好友分享!回本站首页
相关TAG标签 路径 查集
上一篇:Qt事件处理器和事件过滤器实例
下一篇:ZOJ2425
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站