hdu 2874—Connection s between cities(LCA)
2713 ワード
テーマ:nつの都市を提供して、m条路は環が存在しないで、任意の2つの都市の間の距離を求めて、都市間は連絡がないかもしれません.
問題の構想:ST+は集を調べて、都市間の連絡があるかどうかを判断します.与えられたのは森林かもしれません.木のルートを一つのrootに指して、木を構成します.
問題の構想:ST+は集を調べて、都市間の連絡があるかどうかを判断します.与えられたのは森林かもしれません.木のルートを一つのrootに指して、木を構成します.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 10010;
const int M = 25;
const int INF = 99999999;
struct Edge{
int node,len;
Edge*next;
}m_edge[N*2];
int Ecnt;
Edge*head[N];
int tot,ver[2*N],R[2*N],first[N],dir[N];
bool vis[N];
int dp[2*N][M];
int father[N];
//ver: R: first: dir:
void dfs(int u ,int dep)
{
vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
for( Edge*k=head[u]; k ; k = k->next )
if( !vis[k->node] ){
int v = k->node , w = k->len;
dir[v] = dir[u] + w;
dfs(v,dep+1);
ver[++tot] = u; R[tot] = dep;
}
}
// R , R
void ST(int n)
{
for(int i=1;i<=n;i++)
dp[i][0] = i;
for(int j=1;(1< y) swap(x,y);
int res = RMQ(x,y);
return ver[res];
}
void init()
{
Ecnt = tot = 0;
fill( head , head+N , (Edge*)0 );
fill( vis , vis+N , false );
for( int i = 0 ; i < N ; ++i )
father[i] = i;
}
int find( int a )
{
int t = a;
while( father[t] != t ){
father[t] = father[father[t]];
t = father[t];
}
return t;
}
void merge( int a , int b )
{
int t1 = find( a );
int t2 = find( b );
if( t1 != t2 ) father[t1] = t2;
}
void mkEdge( int a , int b , int c )
{
m_edge[Ecnt].node = a;
m_edge[Ecnt].len = c;
m_edge[Ecnt].next = head[b];
head[b] = m_edge + Ecnt++;
m_edge[Ecnt].node = b;
m_edge[Ecnt].len = c;
m_edge[Ecnt].next = head[a];
head[a] = m_edge + Ecnt++;
}
int main()
{
int n,m,p,a,b,c;
while( ~scanf("%d%d%d",&n,&m,&p) ){
init();
for( int i = 0 ; i < m ; ++i ){
scanf("%d%d%d",&a,&b,&c);
mkEdge( a , b , c );
merge( a , b );
}
for( int i = 1 ; i <= n ; ++i ){
if(father[i]!=i) continue;
mkEdge( 0 , i , 0 ); //root 0, 0
}
dir[0] = 0;
dfs( 0 , 1 );
ST( 2*(n+1)-1 );
for( int i = 0 ; i < p ; ++i ){
scanf("%d%d",&a,&b);
if( find(a) != find(b) ){
printf("Not connected
"); continue;
}
c = LCA(a,b);
printf("%d
",dir[a]+dir[b]-2*dir[c]);
}
}
return 0;
}