| 7046118 | 2012-10-30 23:47:29 | Accepted | 31MS | 3988K | C++ |
树和并查集~~
求树中两个点的最近距离 转化成 求两个点的最近公共祖先（LCA）
mindist（u,v)=dist(u)+dist(v)-2*dist(lca(u,v));
向量存储树的邻接点
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 #define MAXN 40004 6 #define MAXM 202 7 int dis[MAXN],father[MAXN]; 8 int visit[MAXN]; 9 int query[MAXM][3];10 struct node11 {12 int length;13 int vex;14 int num;15 };16 vector v[MAXN],q[MAXN];17 int find(int x)18 {19 if(x!=father[x])20 return father[x]=find(father[x]);21 return x;22 }23 void init(int n)24 {25 for(int i=1;i<=n;i++)26 {27 v[i].clear();28 visit[i]=0;29 dis[i]=0;30 father[i]=i;31 }32 }33 void Tarjan(int x)34 {35 visit[x]=1;36 for(vector ::iterator it=q[x].begin();it!=q[x].end();it++)37 {38 if(visit[it->vex])39 query[it->num][2]=find(it->vex);40 }41 for(vector ::iterator it=v[x].begin();it!=v[x].end();it++)42 {43 if(!visit[it->vex])44 {45 dis[it->vex]=dis[x]+it->length;46 Tarjan(it->vex);47 father[it->vex]=x;48 }49 }50 }51 int main()52 {53 int T;54 scanf("%d",&T);55 int n,m;56 57 while(T--)58 {59 scanf("%d%d",&n,&m);60 init(n);61 for(int i=1;i<=n-1;i++)62 {63 int x,y,z;64 scanf("%d%d%d",&x,&y,&z);65 node temp1;temp1.length=z;temp1.vex=y;temp1.num=i;66 node temp2;temp2.length=z;temp2.vex=x;temp2.num=i;67 v[x].push_back(temp1);68 v[y].push_back(temp2);69 }70 for(int i=1;i<=m;i++)71 {72 scanf("%d%d",&query[i][0],&query[i][1]);73 node temp1;temp1.length=0;temp1.vex=query[i][1];temp1.num=i;74 node temp2;temp2.length=0;temp2.vex=query[i][0];temp2.num=i;75 q[query[i][0]].push_back(temp1);76 q[query[i][1]].push_back(temp2);77 }78 Tarjan(1);79 for(int i=1;i<=m;i++)80 printf("%d\n",dis[query[i][0]]+dis[query[i][1]]-2*dis[query[i][2]]);81 82 }83 return 0;84 }
第一篇博客~ 手残啊