LCA

LCA的Tarjan实现

  • emmmm最近公共祖先的实现方式有很多，比如倍增和Tarjan……我感觉后者写起来是比较简单的，好吧事实上我只会后者，所以就只讲一下Tarjan实现LCA的方式吧。复杂度玄学，大概是点的个数加上每一个点所连出来边的数量吧，其实是很快的。

  • 算法的本质其实就是利用DFS对整个图进行遍历，然后在访问过后记录下来每个节点的上一个节点father[x]，如果一对需要求出LCA的点中，一个点已经访问过了，另一个点正在访问，那么访问顺序一定就是从已经访问过的点不断往回退，经过两者的LCA之后向另外一个方向拓展，遇到了正在访问的另一个点，那么因为记录上一个节点的数组father[x]是在回退的过程中记录的，那么因为已经访问过的点肯定回退到了其LCA，否则不经过公共祖先是没有办法访问到另外一个点的。

  • 那么我们就可以通过已经访问过的那个点留下的father[]记录来求出来LCA了，我们只需要不断的往前面的节点走，直到前面的点没有被更新，也就是father[x]=x，这个点就是这一对点的最近公共祖先了。

  • 其实LCA是挺简单的，无论是代码还是理解，其实我觉得我解释的不是很好，所以给上一篇模拟过程的博客吧，用图像来模拟一遍可以加深理解的。

博客链接：LCA 最近公共祖先 : JVxie

  • 还有一点，LCA属于离线算法，但是题目要求按照读入的顺序输出的时候，因为没有办法通过二位数组记录下来两个节点x和y的LCA值，我们就需要在建图的时候，把读入的顺序也记录下来，然后求出来LCA之后，用一维数组按照读入时记录下来的的顺序存到对应的位置，这样一遍for循环就可以输出了。

LCA代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge
{
    int Point;
    int Next;
    int ID;
}a[2000000],b[2000000];
int n,m,q,Link_A[1000000];
int lena,x,y,f[1000000];
int lenb,Link_B[1000000];
int ID[1000000];
bool vis[1000000];
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
void init_First(int x,int y,int z)
{
    a[++lena].Point=y;
    a[lena].Next=Link_A[x];
    a[lena].ID=z;
    Link_A[x]=lena;
    a[++lena].Point=x;
    a[lena].Next=Link_A[y];
    a[lena].ID=z;
    Link_A[y]=lena;
}
void init_Second(int x,int y,int z)
{
    b[++lenb].Point=y;
    b[lenb].Next=Link_B[x];
    b[lenb].ID=z;
    Link_B[x]=lenb;
    b[++lenb].Point=x;
    b[lenb].Next=Link_B[y];
    b[lenb].ID=z;
    Link_B[y]=lenb;
}
int Find(int x)
{
    while(f[x]!=x) x=f[x];
    return x;
}
void Tarjan(int x)
{
    vis[x]=true;
    for(int i=Link_A[x];i;i=a[i].Next)
    if(!vis[a[i].Point])
    {
        Tarjan(a[i].Point);
        f[a[i].Point]=x;
    }
    for(int i=Link_B[x];i;i=b[i].Next)
    {
        if(vis[b[i].Point])
        ID[b[i].ID]=Find(b[i].Point);
    }
}
int main()
{
    n=Read(); m=Read();
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<n;i++)
    {
        x=Read();
        y=Read();
        init_First(x,y,i);
    }
    for(int i=1;i<=m;i++)
    {
        x=Read();
        y=Read();
        init_Second(x,y,i);
    }
    Tarjan(1);
    for(int i=1;i<=m;i++)
    printf("%d\n",ID[i]);
    return 0;
}

NOIP2013 货车运输

题目描述：

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入：

  1. 输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
  2. 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
  3. 接下来一行有一个整数 q，表示有 q 辆货车需要运货。
  4. 接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出：

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

题解：

没有一等奖，肯定要考NOIP啊，写正解这方面，写正解是不可能写正解的，这辈子都不可能写正解的。骗分也不会骗，就是写这种暴力，才能维持到一等分数线的样子。进机房感觉像回家一样，在机房里的感觉比班级里感觉好多了！里面个个都是人才，说话又好听，我超喜欢里面的！ ——码·欧埃尔。

  • 其实这道题，emmmm自己又犯了以前的老错误了，唉，明明还写到了个人签名上面防止犯错，结果还是……这道题拿在手里一般都是直接写暴力了，是的考试的时候我是绝对不会写正解的，就算知道正解该怎么写也是不会写的，因为太容易挂掉了。

  • 算了说说正确的解法吧，其实这道题蛮简单的，就是一遍最大生成树加LCA就可以了。首先我们需要解决求最短路最长的问题，我们可以建立一个最大生成树，这样的话里面的边是可选择边的最大值，这样的话可以保证最短路最长。因为最大生成树是通过从大到小排序边，然后再逐个的选择，所以可以保证最短路最长的，因为选择的边一定是可以选择的最长的。

  • 然后我们就可以在最大生成树上进行LCA了，最大生成树的路径之间是唯一的，所以说我们如果求两个点之间的路径，可以通过O(n)求出LCA，然后利用两者的LCA来直接遍历路径，其核心就在于LCA的father[x]数组，这样可以两个个点都通过father[x]来到达其LCA，中间只需要判断一个最小值就可以了，可谓是非常方便的。

  • 最后需要注意的问题就是，最大生成树不一定是联通的，需要访问每一个联通子图！！！还有在通过father[x]来确定两点之间的路径的时候，一定要想到上面的情况是比较特殊的，需要特别的判断！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int Point;
    int Next;
    int Value;
}a[200000],b[200000];
struct Line
{
    int x;
    int y;
    int v;
}c[200000];
int n,m,Linka[200000],lena;
int x,y,z,q,Linkb[200000],lenb;
int f[200000],ans[200000];
int dis[200000],father[200000];
int fx[200000],fy[200000];
bool vis[200000];
bool mycmp(Line x,Line y)
{ return x.v>y.v; }
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
void init(int x,int y,int z)
{
    a[++lena].Point=y;
    a[lena].Next=Linka[x];
    a[lena].Value=z;
    Linka[x]=lena;
    a[++lena].Point=x;
    a[lena].Next=Linka[y];
    a[lena].Value=z;
    Linka[y]=lena;
}
void Together(int x,int y,int z)
{
    b[++lenb].Point=y;
    b[lenb].Next=Linkb[x];
    b[lenb].Value=z;
    Linkb[x]=lenb;
    b[++lenb].Point=x;
    b[lenb].Next=Linkb[y];
    b[lenb].Value=z;
    Linkb[y]=lenb;
}
int Getfather(int x)
{
    int Truefather=x,That;
    while(Truefather!=father[Truefather])
    Truefather=father[Truefather];
    while(x!=father[x])
    {
        That=father[x];
        father[x]=Truefather;
        x=That;
    }
    return Truefather;
}
void Kruskal()
{
    int all=false;
    for(int i=1;i<=n;i++) father[i]=i;
    sort(c+1,c+m+1,mycmp);
    for(int i=1;i<=m;i++)
    {
        int First=Getfather(c[i].x);
        int Second=Getfather(c[i].y);
        if(First!=Second)
        {
            father[First]=Second;
            init(c[i].x,c[i].y,c[i].v);
            if(++all==n-1) return;
        }
    }
}
int Find(int x)
{
    while(father[x]!=x) x=father[x];
    return x;
}
void LCA(int x)
{
    vis[x]=true;
    for(int i=Linka[x];i;i=a[i].Next)
    if(!vis[a[i].Point])
    {
        dis[a[i].Point]=a[i].Value;
        LCA(a[i].Point);
        father[a[i].Point]=x;
    }
    for(int i=Linkb[x];i;i=b[i].Next)
    {
        if(vis[b[i].Point])
        ans[b[i].Value]=Find(b[i].Point);
    }
}
int Search(int x,int y,int ID)
{
    int Minn=2123456789;
    while(x!=ans[ID])
    {
        if(x==father[x]) return -1;
        Minn=min(Minn,dis[x]);
        x=father[x];
    }
    while(y!=ans[ID])
    {
        if(y==father[y]) return -1;
        Minn=min(Minn,dis[y]);
        y=father[y];
    }
    return Minn;
}
int main()
{
    n=Read(); m=Read();
    for(int i=1;i<=m;i++)
    {
        c[i].x=Read();
        c[i].y=Read();
        c[i].v=Read();
    }
    q=Read();
    Kruskal();
    for(int i=1;i<=q;i++)
    {
        fx[i]=Read();
        fy[i]=Read();
        Together(fx[i],fy[i],i);
    }
    memset(ans,-1,sizeof(ans));
    memset(father,false,sizeof(father));
    for(int i=1;i<=n;i++) father[i]=i;
    for(int i=1;i<=n;i++)
    if(!vis[i]) LCA(i);
    for(int i=1;i<=q;i++)
    cout<<Search(fx[i],fy[i],i)<<'\n';
    return 0;
}