洛谷的刷题日常之P1967

 Algorithm
 

货车运输

这是一道比较综合的题，非常的niubility（我不会做的题都niubility，QWQ），用到的知识包括图论、倍增、贪心、LCA、生成树、并查集。

  • 描述：

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

  • 输入：

第一行有两个用空格隔开的整数n和m，表示A国有n座城市和m条道路。
接下来的m行，每行有3个整数x,y,z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。
注意：x不等于 y，两座城市之间可能有多条道路。

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

接下来的q行，每行有两个整数x、y，用一个空格隔开，表示一辆货车需要从x城市运输货物到y城市。
注意：x不等于y。

  • 输出：

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

  • 输入样例：

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

  • 输出样例：

3
-1
3

  • 解题思路：

    • 贪心：因为要使得货车运的货物尽可能重，所以权值较小的边不会被走过。
    • 图论：根据给出的数据建原始图，然后根据上一步的贪心策略建新图，构造最大生成树。
    • 生成树：构造最大生成树可以使用Kruskal算法。
    • 并查集：Kruskal算法可以用并查集维护节点的连通情况。
    • LCA：在最大生成树上求最近公共祖先，得到两个节点之间最小边权的最大值，即题中的最大载重。
    • 倍增：树上倍增法求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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f

struct road {
    int x,y,z;
}roads[50010];//原始图

struct edge {
    int to,next,w;
}edges[50010];//存储最大生成树的新图

//fa数组表示并查集中的父节点，f数组表示树上的父节点，w数组表示最大载重 
int x,y,cnt,head[10010],fa[10010],f[10010][21],deep[10010],w[10010][21],n,m,q;
bool vis[10010];

//自定义排序规则，边权大的在前面
bool cmp(road x,road y) {
    return x.z>y.z;
}
//前向星存新图
void addroad(int start,int end,int w) {
    edges[++cnt].next=head[start];
    edges[cnt].to=end;
    edges[cnt].w=w;
    head[start]=cnt;
}
//并查集的查找操作
int Find(int x) {
    if(x!=fa[x]) fa[x]=Find(fa[x]);
    return fa[x];
}
//Kruskal算法
void kruskal() {
    sort(roads+1,roads+m+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;//并查集的初始化操作
    for(int i=1;i<=m;i++) {
        //并查集的合并操作
        int a=Find(roads[i].x);
        int b=Find(roads[i].y);
        if(a!=b) {
            fa[a]=b;
            //无向图，双向边
            addroad(roads[i].x,roads[i].y,roads[i].z);
            addroad(roads[i].y,roads[i].x,roads[i].z);
        }
    }
}
//预处理：从根节点进行搜索，求节点深度
void dfs(int node) {
    vis[node]=true;
    for(int i=head[node];i;i=edges[i].next) {//前向星遍历
        int to=edges[i].to;
        if(vis[to]) continue;
        deep[to]=deep[node]+1;//计算深度
        f[to][0]=node;//存父节点
        w[to][0]=edges[i].w;//存节点到父节点的权值
        dfs(to);
    }
}
//树上倍增法优化求解LCA问题
int lca(int x,int y) {
    int a=Find(x);
    int b=Find(y);
    if(a!=b) return -1;//不连通输出-1
    int ans=INF;
    if(deep[x]>deep[y]) swap(x,y);//始终使得y节点更深
    //将y节点提到与x节点相同的深度
    for(int i=20;i>=0;i--) {
        if(deep[f[y][i]]>=deep[x]) {
            ans=min(ans,w[y][i]);//更新最大载重（最小边权）
            y=f[y][i];//修改y的位置
        }
    }
    if(x==y) return ans;//如果位置已经相等，直接返回答案
    //寻找公共祖先
    for(int i=20;i>=0;i--) {
        if(f[x][i]!=f[y][i]) {
            ans=min(ans,min(w[x][i],w[y][i]));//更新最大载重（最小边权）
            x=f[x][i];//修改x的位置
            y=f[y][i];//修改y的位置
        }
    }
    ans=min(ans,min(w[x][0],w[y][0]));//更新x,y到公共祖先的最大载重，fa[x][0]、fa[y][0]即为公共祖先 
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {//存原始图
        scanf("%d%d%d",&roads[i].x,&roads[i].y,&roads[i].z);
    }
    kruskal();
    for(int i=1;i<=n;i++) {//预处理
        if(!vis[i]) {
            deep[i]=1;
            dfs(i);
            f[i][0]=i;
            w[i][0]=INF;
        }
    }
    //LCA初始化
    for(int i=1;i<=20;i++) {
        for(int j=1;j<=n;j++) {
            f[j][i]=f[f[j][i-1]][i-1];
            w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));//O(logn)复杂度回答询问
    }
    return 0;
}
 Previous

Dynamic Programming Simulation