Hdu 2874 Connections between cities (数据结构_LCA)
2012-07-20 09:19:35      个评论

5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

C艹代码：
[cpp]
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MIN 11000
#define MAX 1100000

struct node {

int v,len;
}cur;
int dist[MIN],visit[MIN];         //dist[i]表示i到根节点的距离，visit[i]判断是否遍历过
int n,m,q,ans[MAX],fa[MIN];       //ans[i]记录第i组查询应该输出什么
vector<node> tree[MIN],query[MIN];//tree记录森林，query记录查询

void Initial() {

memset(dist,0,sizeof(dist));
memset(visit,0,sizeof(visit));
for (int i = 0; i <= n; ++i)
fa[i] = i,tree[i].clear(),query[i].clear();

void AddEdge(int a,int b,int c,int kind) {

if (kind == 0) {
//建树
cur.v = b,cur.len = c;
tree[a].push_back(cur);
}
else {
//离线查询序列
cur.v = b,cur.len = c;
query[a].push_back(cur);
}

int Find(int n) {
//并查集找父节点，并进行路径压缩
int x = n,r;
while (fa[x] != x) x = fa[x];
while (n != x) {

r = fa[n];
fa[n] = x,n = r;
}
return x;

void Tarjan(int now,int dis,int root) {

fa[now] = now;
dist[now] = dis;
visit[now] = root;

node fuck;
int size = tree[now].size();
for (int i = 0; i < size; ++i) {

fuck = tree[now][i];
if (!visit[fuck.v]) {

Tarjan(fuck.v,dis+fuck.len,root);
fa[fuck.v] = now;
}
}

size = query[now].size();
for (int i = 0; i < size; ++i){

fuck = query[now][i];
if (visit[fuck.v]) {                                    //a->b,b如果未遍历，那么b->a的时候还可以计算

if (visit[fuck.v] != root) ans[fuck.len] = -1;      //在不同分支中
else ans[fuck.len] = dist[now] + dist[fuck.v] - 2 * dist[Find(fuck.v)];
}
}

int main()

int i,j,k;
int ta,tb,a,b,c;

while (scanf("%d%d%d",&n,&m,&q) != EOF) {

Initial();
for (i = 1; i <= m; ++i) {

scanf("%d%d%d",&a,&b,&c);
}

for (i = 1; i <= q; ++i) {

scanf("%d%d",&a,&b);
}

//Tarjan求解
for (i = 1; i <= n; ++i)
if (!visit[i]) Tarjan(i,0,i);   //以i为根遍历整棵树

for (i = 1; i <= q; ++i)   www.2cto.com
if (ans[i] != -1) printf("%d\n",ans[i]);
else printf("Not connected\n");
}