程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 周賽 HDU 2874 HDU 2586 LCA

周賽 HDU 2874 HDU 2586 LCA

編輯:C++入門知識

因為涉及到算法,所以就不把全部題目放到一個文章裡了,方便以後找相關算法的時候查看。

HDU 2874

題意:給定一些點和邊,詢問兩點之間是否連通,若連通,輸出最短距離。

思路:離線tarjan算法,與其他裸題的區別就是要判是否在一棵樹上。


[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 100005  
#define inf 1<<28  
#define LL(x) (x<<1)  
#define RR(x) (x<<1|1)  
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
struct kdq 

    int e,l,next ; 
} ed[Max] ,ee[2000005] ; 
int head1[Max] ; 
int nume = 0 ; 
int head[Max] ; 
int vis[Max] ; 
int num ; 
int dis[Max] ; 
int f[Max] ; 
int ans[Max * 10] ; 
 
void add(int s ,int e, int l) 

    ed[num].e = e ; 
    ed[num].l = l ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 

void adde(int s,int e,int l ) 

    ee[nume].e = e ; 
    ee[nume].next = head1[s] ; 
    ee[nume].l = l ; 
    head1[s] = nume ++ ; 

int aaa ; 
void init(int n ) 

    mem(head,-1); 
    mem(head1 ,-1) ; 
    nume = 0 ; 
    mem(vis,0) ; 
    num = 0 ; 
    mem(dis,0) ; 
    for (int i = 0 ; i <= n; i++)f[i] = i ; 
    mem(ans,0) ; 

 
int find(int x ) 

    return x == f[x] ? x :f[x] = find(f[x]) ; 

int nnn ; 
void dfs(int now,int pre,int l) 

    //cout <<nnn<<endl;  
    dis[now] = dis[pre] + l ; 
    for (int i = head[now] ; i != -1 ; i = ed[i].next ) 
    { 
        int e = ed[i].e ; 
        int l = ed[i].l ; 
        if(e == pre)continue; 
        dfs(e,now,l) ; 
        f[e] = now ; 
    } 
    vis[now] = nnn ; 
   // cout <<vis[now]<<endl;  
    for (int i = head1[now] ; i != -1 ;i = ee[i].next ) 
    { 
        int e = ee[i].e; 
 
        if(vis[e]) 
        { 
            //cout <<vis[e]<<endl;  
            if(find(e) == aaa||vis[e] == nnn)//判斷是否在這棵樹上找到該點  
            ans[ee[i].l] = dis[e] + dis[now] - 2 * dis[find(e)] ; 
            else ans[ee[i].l] = -1 ; 
        } 
    } 

int main() 

    int  T ; 
    int n ,m , k ; 
    while(scanf("%d%d%d",&n,&m,&k) != EOF) 
    { 
        init(n) ; 
        for (int i = 0 ; i < m ; i ++) 
        { 
            int a , b , c ; 
            scanf("%d%d%d",&a,&b,&c) ; 
            add(a,b,c) ; 
            add(b,a,c) ; 
        } 
        for (int i = 0 ; i < k ; i ++) 
        { 
            int a ,b ; 
            scanf("%d%d",&a,&b); 
            adde(a,b,i); 
            adde(b,a,i) ; 
 
        } 
       nnn = 1 ; 
       for (int i = 1 ;i <= n ;i ++) 
       { 
           if(!vis[i]) 
           { 
               aaa = i ; 
               nnn ++ ; 
               dfs(i,0,0) ; 
 
           } 
       } 
        for (int i = 0 ; i < k ; i ++) 
            if(ans[i] == -1 ) 
                puts("Not connected"); 
            else 
                printf("%d\n",ans[i]) ; 
    } 
 
    return 0; 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

struct kdq
{
    int e,l,next ;
} ed[Max] ,ee[2000005] ;
int head1[Max] ;
int nume = 0 ;
int head[Max] ;
int vis[Max] ;
int num ;
int dis[Max] ;
int f[Max] ;
int ans[Max * 10] ;

void add(int s ,int e, int l)
{
    ed[num].e = e ;
    ed[num].l = l ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}
void adde(int s,int e,int l )
{
    ee[nume].e = e ;
    ee[nume].next = head1[s] ;
    ee[nume].l = l ;
    head1[s] = nume ++ ;
}
int aaa ;
void init(int n )
{
    mem(head,-1);
    mem(head1 ,-1) ;
    nume = 0 ;
    mem(vis,0) ;
    num = 0 ;
    mem(dis,0) ;
    for (int i = 0 ; i <= n; i++)f[i] = i ;
    mem(ans,0) ;
}

int find(int x )
{
    return x == f[x] ? x :f[x] = find(f[x]) ;
}
int nnn ;
void dfs(int now,int pre,int l)
{
    //cout <<nnn<<endl;
    dis[now] = dis[pre] + l ;
    for (int i = head[now] ; i != -1 ; i = ed[i].next )
    {
        int e = ed[i].e ;
        int l = ed[i].l ;
        if(e == pre)continue;
        dfs(e,now,l) ;
        f[e] = now ;
    }
    vis[now] = nnn ;
   // cout <<vis[now]<<endl;
    for (int i = head1[now] ; i != -1 ;i = ee[i].next )
    {
        int e = ee[i].e;

        if(vis[e])
        {
            //cout <<vis[e]<<endl;
            if(find(e) == aaa||vis[e] == nnn)//判斷是否在這棵樹上找到該點
            ans[ee[i].l] = dis[e] + dis[now] - 2 * dis[find(e)] ;
            else ans[ee[i].l] = -1 ;
        }
    }
}
int main()
{
    int  T ;
    int n ,m , k ;
    while(scanf("%d%d%d",&n,&m,&k) != EOF)
    {
        init(n) ;
        for (int i = 0 ; i < m ; i ++)
        {
            int a , b , c ;
            scanf("%d%d%d",&a,&b,&c) ;
            add(a,b,c) ;
            add(b,a,c) ;
        }
        for (int i = 0 ; i < k ; i ++)
        {
            int a ,b ;
            scanf("%d%d",&a,&b);
            adde(a,b,i);
            adde(b,a,i) ;

        }
       nnn = 1 ;
       for (int i = 1 ;i <= n ;i ++)
       {
           if(!vis[i])
           {
               aaa = i ;
               nnn ++ ;
               dfs(i,0,0) ;

           }
       }
        for (int i = 0 ; i < k ; i ++)
            if(ans[i] == -1 )
                puts("Not connected");
            else
                printf("%d\n",ans[i]) ;
    }

    return 0;
}


HDU 2586

裸題


[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 100005  
#define inf 1<<28  
#define LL(x) (x<<1)  
#define RR(x) (x<<1|1)  
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
struct kdq 

    int e,l,next ; 
}ed[Max] ; 
int head[Max] ; 
bool vis[Max] ; 
int num ; 
int dis[Max] ; 
int f[Max] ; 
int ans[Max] ; 
 
void add(int s ,int e, int l) 

    ed[num].e = e ; 
    ed[num].l = l ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 

vector<PII>q[Max];; 
void init(int n ) 

    mem(head,-1); 
    mem(vis,0) ; 
    num = 0 ; 
    mem(dis,0) ; 
    for (int i = 0 ;i <= n; i++)f[i] = i ,q[i].clear() ; 
    mem(ans,0) ; 

 
 
int find(int x ) 

    return x == f[x] ? x :f[x] = find(f[x]) ; 

int dfs(int now,int pre) 

    for (int i = head[now] ;i != -1 ;i = ed[i].next ) 
    { 
        int e = ed[i].e ; 
        int l = ed[i].l ; 
        if(e == pre)continue; 
        dis[e] = dis[now] + l ; 
        dfs(e,now) ; 
        f[e] = now ; 
    } 
    vis[now] = 1 ; 
    int k = q[now].size() ; 
    for (int i = 0 ;i < k ;i ++) 
    { 
        int e = q[now][i].first ; 
        if(vis[e]) 
        { 
            ans[q[now][i].second] = dis[e] + dis[now] - 2 * dis[find(e)] ; 
        } 
    } 

int main() 

    int  T ; 
    cin >> T ; 
    while( T -- ) 
    { 
        int n ,m ; 
        cin >> n >> m ; 
        init(n) ; 
        for (int i = 0 ;i < n - 1 ;i ++) 
        { 
            int a , b , c ; 
            scanf("%d%d%d",&a,&b,&c) ; 
            add(a,b,c) ; 
            add(b,a,c) ; 
        } 
        for (int i = 0 ;i < m ;i ++) 
        { 
            int a ,b ; 
            scanf("%d%d",&a,&b); 
            q[a].push_back(mp(b,i)) ; 
            q[b].push_back(mp(a,i)) ; 
        } 
        dfs(1,0) ; 
        for (int i = 0 ;i < m ;i ++) 
        cout <<ans[i]<<endl; 
    } 
    return 0; 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

struct kdq
{
    int e,l,next ;
}ed[Max] ;
int head[Max] ;
bool vis[Max] ;
int num ;
int dis[Max] ;
int f[Max] ;
int ans[Max] ;

void add(int s ,int e, int l)
{
    ed[num].e = e ;
    ed[num].l = l ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}
vector<PII>q[Max];;
void init(int n )
{
    mem(head,-1);
    mem(vis,0) ;
    num = 0 ;
    mem(dis,0) ;
    for (int i = 0 ;i <= n; i++)f[i] = i ,q[i].clear() ;
    mem(ans,0) ;
}


int find(int x )
{
    return x == f[x] ? x :f[x] = find(f[x]) ;
}
int dfs(int now,int pre)
{
    for (int i = head[now] ;i != -1 ;i = ed[i].next )
    {
        int e = ed[i].e ;
        int l = ed[i].l ;
        if(e == pre)continue;
        dis[e] = dis[now] + l ;
        dfs(e,now) ;
        f[e] = now ;
    }
    vis[now] = 1 ;
    int k = q[now].size() ;
    for (int i = 0 ;i < k ;i ++)
    {
        int e = q[now][i].first ;
        if(vis[e])
        {
            ans[q[now][i].second] = dis[e] + dis[now] - 2 * dis[find(e)] ;
        }
    }
}
int main()
{
    int  T ;
    cin >> T ;
    while( T -- )
    {
        int n ,m ;
        cin >> n >> m ;
        init(n) ;
        for (int i = 0 ;i < n - 1 ;i ++)
        {
            int a , b , c ;
            scanf("%d%d%d",&a,&b,&c) ;
            add(a,b,c) ;
            add(b,a,c) ;
        }
        for (int i = 0 ;i < m ;i ++)
        {
            int a ,b ;
            scanf("%d%d",&a,&b);
            q[a].push_back(mp(b,i)) ;
            q[b].push_back(mp(a,i)) ;
        }
        dfs(1,0) ;
        for (int i = 0 ;i < m ;i ++)
        cout <<ans[i]<<endl;
    }
    return 0;
}


 

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