程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3728 tarjan+帶權路徑並查集

poj 3728 tarjan+帶權路徑並查集

編輯:C++入門知識

[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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved