周赛 HDU 2874 HDU 2586 LCA - c++编程基础

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 < 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 < for (int i = head1[now] ; i != -1 ;i = ee[i].next )
{
int e = ee[i].e;

if(vis[e])
{
//cout < 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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
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 ++ ;
}
vectorq[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 < }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P

周赛 HDU 2874 HDU 2586 LCA (二)