因為涉及到算法，所以就不把全部題目放到一個文章裡了，方便以後找相關算法的時候查看。
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;
}
