2022暑期训练题单（基本算法）Day1~2

矩阵快速幂

题目背景

矩阵快速幂

题目描述

给定 $n\times n$ 的矩阵 $A$，求 $A^k$。

输入格式

第一行两个整数 $n,k$
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。

输出格式

输出 $A^k$

共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k{)}_{i,j}$，每个元素对 $10^9+7$ 取模。

样例 #1

样例输入 #1

2 1
1 1
1 1
1
2
3

样例输出 #1

1 1
1 1
1
2

提示

【数据范围】
对于 $100\%$ 的数据：$1\le n\le 100$，$0\le k\le 10^{12}$

主要思路

#include
#include
#include
using namespace std;
typedef long long ll;
ll n,k;
const ll mod=1e9+7;
struct node
{
    ll m[110][110];
}a,ans;
node mul(node a,node b)
{
    node now;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            now.m[i][j]=0;
            for(int k=1;k<=n;k++)
            {
                now.m[i][j]=(now.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
            }
        }
    }
    return now;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>a.m[i][j];
            if(i==j)
                ans.m[i][j]=1;
            else ans.m[i][j]=0;
        }
    while(k)
    {
        if(k&1) ans=mul(ans,a);
        k>>=1;
        a=mul(a,a);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<ans.m[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}
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

取石子

题目描述

Alice 和 Bob 在玩游戏。

他们有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，保证初始时 $a_i\le a_{i+1}(1\le i<n)$。现在他们轮流对这些石子进行操作，每次操作人可以选择满足 $a_i>a_{i-1}$（$a_0$ 视为 $0$）的一堆石子，并从中取走一个。谁最后不能取了谁输。Alice 先手，他们都使用最优策略，请判断最后谁会取得胜利。

输入格式

第一行一个整数 $n(1\le n\le 100)$，表示石子堆数。

接下来一行 $n$ 个数，第 $i$ 个数为 $a_i(1\le a_i\le 10^9)$，意义如上所述。

输出格式

“Alice” 或 “Bob”，表示谁会赢。

样例 #1

样例输入 #1

1
1
1
2

样例输出 #1

Alice
1

样例 #2

样例输入 #2

1
2
1
2

样例输出 #2

Bob
1

主要思路：

可以发现，主要还有石子就一直能取走，所以只用判断石子总数的奇偶即可。

智力大冲浪

题目描述

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 $m$ 元。先不要太高兴，因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：

首先，比赛时间分为 $n$ 个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 $t_i$ 前完成。如果一个游戏没能在规定期限前完成，则要从奖励费 $m$ 元中扣去一部分钱 $w_i$，$w_i$ 为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!

输入格式

第一行为 $m$，表示一开始奖励给每位参赛者的钱；

第二行为 $n$，表示有 $n$ 个小游戏；

第三行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 的规定完成期限；

第四行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 不能在规定期限前完成的扣款数。

输出格式

输出仅一行，表示小伟能赢取最多的钱。

样例 #1

样例输入 #1

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
1
2
3
4

样例输出 #1

9950
1

提示

对于 $100\%$ 的数据，$1\le n\le 500$，$1\le m\le 5\times 10^5$，$1\le t_i\le n$，$1\le w_i\le 1000$。

主要思路

#include
#include
#include
using namespace std;
typedef long long ll;
unordered_map<ll,ll> book;
typedef pair<ll,ll> pa;
pa a[500010];
int main()
{
    ll m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].second;
    for(int i=1;i<=n;i++)
        cin>>a[i].first;
    sort(a+1,a+1+n);
    for(int i=n;i;i--)
    {
        ll last=a[i].second;
        while(book[last]) last--;
        if(last) book[last]=1;
        else m-=a[i].first;
    }
    cout<<max(0ll,m)<<endl;
    return 0;
}
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

绝世好题

题目描述

给定一个长度为 $n$ 的数列 $a_i$，求 $a_i$ 的子序列 $b_i$ 的最长长度 $k$，满足 $b_i & b_{i-1} \ne 0 $，其中 $2\le i\le k$， $\&$ 表示位运算取与。

输入格式

输入文件共 2 行。
第一行包括一个整数 $n$。
第二行包括 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

输出文件共一行。
包括一个整数，表示子序列 $b_i$ 的最长长度。

样例 #1

样例输入 #1

3
1 2 3
1
2

样例输出 #1

2
1

提示

对于100%的数据，$1\le n\le 100000$，$a_i\le 10^9$。

主要思路

主要利用数位dp的思想，主要从0位开始遍历。

#include
#include
#include
using namespace std;
int n;
int a[100010];
int b[40];
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int now=0;
        for(int j=0;j<32;j++)
        {
            if((a[i]>>j)&1) now=max(now,b[j]+1);
        }
        for(int j=0;j<32;j++)
        {
            if((a[i]>>j)&1) b[j]=max(b[j],now);
        }
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}
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

[HAOI2008]糖果传递

题目描述

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

输入格式

小朋友个数 $n$，下面 $n$ 行 $a_i$。

输出格式

求使所有人获得均等糖果的最小代价。

样例 #1

样例输入 #1

4
1
2
5
4
1
2
3
4
5

样例输出 #1

4
1

提示

对于 $100\%$ 的数据 $n\le 10^6$。

主要思路

采用均分纸牌的思想，假设每一个原来有$A_i$个糖果的小朋友都向左传递糖果$X_i$,那么$X_i=X_{i+1}+A_i-ave$,由此可得$X_2=ave-A_1+X_1,X_3=ave-A_2+X_2=2\ast ave-A_1-A_2+X_1.$
将$C_i={\sum }_1^i{X}_i-i\ast ave$预处理出来，令$|X_i|$最小，即令$|X_1-C_i|$最小，则$X_1$取$C_i$的中位数即可。

#include
#include
#include
using namespace std;
typedef long long ll;
ll n;
ll a[1000010],c[1000010];
int main()
{
    cin>>n;
    ll ave=0;
    for(int i=1;i<=n;i++)
        cin>>a[i],ave+=a[i];
    ave/=n;
    for(int i=1;i<=n;i++)
        c[i]=ave-a[i-1]+c[i-1];
    sort(c+1,c+1+n);
    ll mid=c[n/2];
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=abs(mid-c[i]);
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

「EZEC-2」异或

题目描述

有 $T$ 组询问，每次给定两个正整数 $n,l$，

你需要构造一个长度为 $l$ 的正整数序列 $a$（编号从 $1$ 至 $l$），

且满足 $\forall i\in [1,l]$，都有 $a_i\in [1,n]$。

求：

$$\sum _{i=1}^l\sum _{j=1}^{i-1}{a}_i\oplus a_j$$

的最大值。

为了避免答案过大，对于每组询问，只需要输出这个最大值对 $10^9+7$ 取模的结果。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来第 $2$ 行到第 $T+1$ 行，每行两个整数 $n,l$ ，分别代表 $a_i$ 的最大取值与 $a$ 的长度。

输出格式

共 $T$ 行，每行一个整数，对应每组询问的答案对 $10^9+7$ 取模的结果。

样例 #1

样例输入 #1

1
2 3
1
2

样例输出 #1

6
1

样例 #2

样例输入 #2

2
114 514
1919 180
1
2
3

样例输出 #2

8388223
16580700
1
2

提示

【样例解释 #1】
当 $n=2,l=3$，$a$ 取 { 1 , 2 , 1 } \{1,2,1\} {1,2,1} 的任一排列时可以得到最大值，为 $(1\oplus 2)+(1\oplus 1)+(2\oplus 1)=6$，易证明此时原式有最大值。

---

【数据规模与约定】

对于 $100\%$ 的数据，满足 $1\le T\le 5\times 10^5$，$1\le n\le 10^{12}$，$2\le l\le 10^5$。

---

【提示】

1. 「$\oplus$」是按位异或符号。如果您不知道什么是按位异或，可以参考这里。
2. 取模是一种运算，$a$ 对 $b$ 取模代表将 $a$ 赋值为 $a$ 除以 $b$ 所得到的余数。
   在 C++ / Python 中的取模符号为 %，在 Pascal 中的取模符号为 mod。
3. $\sum$ 是求和符号。如果您不知道什么是 $\sum$ 符号，可以参考这里。
4. 请注意数据的读入输出对程序效率造成的影响。

主要思路

#include
#include
#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,l;
        cin>>n>>l;
        if(n==1) cout<<0<<endl; // 不能等于0，只能全等于1，异或结果为0；
        else
            cout<<(l/2*(l-l/2)%mod)*(qpow(2,log2(n)+1)-1)%mod<<endl;
    }
    return 0;
}
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

[NOIP2012 提高组] 借教室

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n,m$，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。

样例 #1

样例输入 #1

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

样例输出 #1

-1 
2
1
2

提示

【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2 $天到第 $4$ 天每天提供$ 3 $个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第$2$ 个申请人修改订单。

【数据范围】

对于10%的数据，有$1\le n,m\le 10$；

对于30%的数据，有$1\le n,m\le 1000$；

对于 70%的数据，有$1\le n,m\le 10^5$；

对于 100%的数据，有$1\le n,m\le 10^6,0\le r_i,d_j\le 10^9,1\le s_j\le t_j\le n$。

NOIP 2012 提高组 第二天 第二题

2022.2.20 新增一组 hack 数据

主要思路

①差分+二分

#include
#include
#include
using namespace std;
typedef long long ll;
ll n,m;
ll a[1000010],d[1000010],s[1000010],t[1000010];
ll b[1000010];
bool find(int x)
{
    memset(b,0,sizeof(b));
    for(int i=1;i<=x;i++)
    {
        b[s[i]]+=d[i];
        b[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        if(b[i]>a[i]) return 0;
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>d[i]>>s[i]>>t[i];
    if(find(m))
        cout<<0<<endl;
    else
    {
        int l=0,r=m;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(find(mid)) l=mid;
            else r=mid-1;
        }
        cout<<-1<<endl;
        cout<<l+1<<endl;
    }
    return 0;
}
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

②线段树(有一个点超时)

#include
#include
using namespace std;
typedef long long ll;
ll n,m;
struct node
{
    ll l,r,minx,add;
}tr[4000010];
ll a[1000010];
void pushup(int u)
{
    tr[u].minx=min(tr[u<<1].minx,tr[u<<1|1].minx);
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[l],0};
    else
    {
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void pushdown(int u)
{
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add)
    {
        left.add+=root.add,left.minx-=root.add;
        right.add+=root.add,right.minx-=root.add;
        root.add=0;
    }
}
void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].minx-=d;
        tr[u].add+=d;
    }
    else
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,d);
        if(r>=mid+1) modify(u<<1|1,l,r,d);
        pushup(u);
    }
}
ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minx;
    pushdown(u);
    ll ans=1e9;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) ans=min(ans,query(u<<1,l,r));
    if(r>=mid+1) ans=min(ans,query(u<<1|1,l,r));
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    int book=0;
    for(int i=1;i<=m;i++)
    {
        int d,l,r;
        cin>>d>>l>>r;
        if(!book)
        {
            int nowmin=query(1,l,r);
            if(nowmin<d)
            {
                book=i;
            }
            else
            {
                modify(1,l,r,d);
            }
        }
    }
    if(book) cout<<-1<<'\n'<<book<<'\n';
    else cout<<0<<'\n';
    return 0;
}
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

[TJOI2017]可乐

题目描述

加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

输入格式

第一行输入两个正整数 $N$，$M$。$N$ 表示城市个数，$M$ 表示道路个数。

接下来 $M$ 行每行两个整数 $u$，$v$，表示 $u$，$v$ 之间有一条道路。保证两座城市之间只有一条路相连，且没有任何一条道路连接两个相同的城市。

最后一行是一个整数 $t$，表示经过的时间。

输出格式

输出可乐机器人的行为方案数，答案可能很大，请输出对 $2017$ 取模后的结果。

样例 #1

样例输入 #1

3 2
1 2
2 3
2
1
2
3
4

样例输出 #1

8
1

提示

样例输入输出 1 解释

• $1$ ->爆炸。
• $1$ -> $1$ ->爆炸。
• $1$ -> $2$ ->爆炸。
• $1$ -> $1$ -> $1$。
• $1$ -> $1$ -> $2$。
• $1$ -> $2$ -> $1$。
• $1$ -> $2$ -> $2$。
• $1$ -> $2$ -> $3$。

---

数据范围与约定

• 对于 $20\%$ 的数据，保证 $t\le 1000$。
• 对于$100\%$的数据，保证 $1<t\le 10^6$，$1\le N\le 30$，$0<M<100$，$1\le u,v\le N$。

主要思路

救命，这竟然是一道矩阵快速幂的题。
这个题目的思想很奇妙，采用矩阵乘法计算有可能的方案数。
首先是一个全零矩阵，x-y之间有道路的话就将a[x][y]=1，如果在x处自爆的话就相当于有一个x-0的道路，如果在x处停留的话就相当于x点存在一个自环。
PS:为什么0-0也要连接一个自环呢？
比如2s时，1-0，1-1-0，1-2-0可以有三种情况，但是第一种只用1s，最后的结果将不会计算，所以给0点添加自环，以此达到时间的平衡。

#include
#include
using namespace std;
typedef long long ll;
ll n,m;
const ll mod=2017;
struct M
{
    ll m[40][40];
}a,ans;
M mul(M a,M b)
{
    M ans;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            ans.m[i][j]=0;
            for(int k=0;k<=n;k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    // 所有0-n的自环
    for(int i=0;i<=n;i++)
        a.m[i][i]=1,a.m[i][0]=1;
    for(int i=0;i<=n;i++)
        ans.m[i][i]=1;
    while(m--)
    {
        ll x,y;
        cin>>x>>y;
        a.m[x][y]=1;
        a.m[y][x]=1;
    }
    ll t;
    cin>>t;
    while(t)
    {
        if(t&1) ans=mul(ans,a);
        t>>=1;
        a=mul(a,a);
    }
    ll anss=0;
    for(int i=0;i<=n;i++)
        anss=(anss+ans.m[1][i])%mod;
    cout<<anss<<endl;
    return 0;
}
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

[NOIP2013 提高组] 货车运输

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 $A$ 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x,y,z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x\ne y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x\ne y$

输出格式

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

样例 #1

样例输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
1
2
3
4
5
6
7
8

样例输出 #1

3
-1
3
1
2
3

提示

对于 $30\%$ 的数据，$1\le n<1000$，$1\le m<10,000$，$1\le q<1000$；

对于 $60\%$ 的数据，$1\le n<1000$，$1\le m<5\times 10^4$，$1\le q<1000$；

对于 $100\%$ 的数据，$1\le n<10^4$，$1\le m<5\times 10^4$，$1\le q<3\times 10^4$，$0\le z\le 10^5$。

主要思路：

①最大生成树+lca
看了算法标签，发现有lca，由于两个城市之间道路不唯一，所以要构造最大生成树。但是这道题有个很恶心的地方，城市之间不一定联通，也就是说会有好多个树，这一点我不知道该怎么解决。
其实在lca的时候，还是用lca的板子就可以的，不用每一颗树都开一个数组，因为每个城市的标号都不一样。

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll n,m;
vector<ll> l[10010],w[10010];
struct node
{
	ll x,y,z;
}a[100010];
bool cmp(node a,node b)
{
	return a.z>b.z;
}
ll f[10010];
ll find(ll k)
{
	if(f[k]==k) return k;
	return f[k]=find(f[k]);
}
ll depth[10010],fa[10010][40],maxa[10010][40];
void bfs(int x)
{
	queue<ll> q;
	q.push(x);
	depth[x]=1;
	while(q.size())
	{
		ll now=q.front();
		q.pop();
		for(int i=0;i<l[now].size();i++)
		{
			ll ne=l[now][i];
			if(depth[ne]>depth[now]+1)
			{
				depth[ne]=depth[now]+1;
				q.push(ne);
				fa[ne][0]=now;
				maxa[ne][0]=w[now][i];
				for(int j=1;j<32;j++)
				{
					// 维护祖先
					fa[ne][j]=fa[fa[ne][j-1]][j-1];
					// 维护道路权值
					maxa[ne][j]=min(maxa[fa[ne][j-1]][j-1],maxa[ne][j-1]);
				}
			}
		}
	}
}
ll lca(ll x,ll y)
{
	ll ans=1e9;
	if(depth[x]<depth[y]) swap(x,y);
	for(int i=31;i>=0;i--)
	{
		if(depth[fa[x][i]]>=depth[y])
		{
			ans=min(ans,maxa[x][i]);
			x=fa[x][i];
		}
	}
	if(x==y) return ans;
	for(int i=31;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			ans=min(ans,min(maxa[x][i],maxa[y][i]));
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return min(ans,min(maxa[x][0],maxa[y][0]));
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	// 构建最大生成树
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=a[i].x,y=a[i].y;
		if(find(x)!=find(y))
		{
			f[find(x)]=find(y);
			l[x].push_back(y);
			l[y].push_back(x);
			w[x].push_back(a[i].z);
			w[y].push_back(a[i].z);
		}
	}
	// 进行lca预处理
	memset(depth,0x3f,sizeof(depth));
	depth[0]=0;
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
			bfs(i);
	}
	ll q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(f[x]!=f[y])
			cout<<-1<<endl;
		else
		{
			cout<<lca(x,y)<<endl;
		}
	}
	return 0;
}
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

②启发式合并