NOIP2013货车运输 题解

题目链接

简述题意,就是一张无向图,每条边又一个边权。

每组询问要求找到任意两点的一条路径,使得这条路上面最小的边权是所有路径中最大的。

前30%的数据,可以直接SPFA暴力。

正解的话……

考虑贪心,任意两点的路径尽量走较大的,于是可以构建一棵最大生成树,容易理解,这条路一定在最大生成树上。

对于一棵树,任意两点都有唯一路径,这条路径长度的话,可以通过$\log{n}$的倍增求得LCA来做。

题目要求是求出这条路径上面最小的一条边权。

还是考虑倍增,LCA中构建了一个father[n][i]表示以此节点向上$2^i$个父亲的节点。本题既然要求询问最小的边权,可以构建一个value[n][i]数组,表示以从此结点到以此节点向上$2^i$个父亲的节点的路径上最小的一条边的边权。

上述的两个数组均可以dfs预处理得到。

对于点是否连通,开个并查集判断一下就可以了!毕竟做生成树的时候也要用到并查集。

放上AC代码

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
156
157
158
159
160
161
162
163
164
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdlib>

const int inf=0x7fffffff;
const int maxn=1e5+10;
const int maxlog=25;

typedef struct EdgeNode //链式边表
{
int to,val;
EdgeNode *next;
EdgeNode(int to,int w,EdgeNode *nxt):to(to),val(w)
{
next=nxt;
}
}*Edge;

struct EDGE
{
int u,v,val;
bool operator >(const EDGE &tmp) const
{
return val>tmp.val;
}
};

std::vector<EDGE> E; //存边

class UnionFind //并查集
{
private:
int father[maxn];

int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}

public:
void init(int n)
{
for(int i=1;i<=n;i++)
father[i]=i;
}

bool SameSet(int x,int y)
{
return find(x)==find(y);
}

void Union(int x,int y)
{
father[find(x)]=find(y);
}

}PointSet;

int n,m;
Edge head[maxn];

inline void add(int u,int v,int w)
{
head[u]=new EdgeNode(v,w,head[u]);
head[v]=new EdgeNode(u,w,head[v]);
}

void MaxTree() //最大生成树
{
int cnt=0;
PointSet.init(n);
std::sort(E.begin(),E.end(),std::greater<EDGE>());
for(auto it : E)
{
int u=it.u,v=it.v,w=it.val;
if(!PointSet.SameSet(u,v))
{
PointSet.Union(u,v);
cnt++;
add(u,v,w);
if(cnt==n-1)
return;
}
}
}

int father[maxn][maxlog]; //倍增父亲节点
int depth[maxn]; //深度
int value[maxn][maxlog]; //倍增最小边

void dfs(int pos,int dad,int val)
{
depth[pos]=depth[dad]+1;
father[pos][0]=dad;
value[pos][0]=val;
for(int i=1;i<maxlog;i++)
{
father[pos][i]=father[father[pos][i-1]][i-1];
value[pos][i]=std::min(value[pos][i-1],value[father[pos][i-1]][i-1]);
/*预处理父亲节点和最小边权*/
}

for(Edge node=head[pos];node;node=node->next)
if(node->to!=dad)
dfs(node->to,pos,node->val);
}

int get_ans(int x,int y) //倍增查询
{
int ans=inf;//用于更新最小边权
if(depth[x]<depth[y])
std::swap(x,y);
for(int i=maxlog-1;i>=0;i--)
if(depth[father[x][i]]>=depth[y])
{
ans=std::min(ans,value[x][i]);
x=father[x][i];
}
if(x==y)
return ans;
for(int i=maxlog-1;i>=0;i--)
if(father[x][i]!=father[y][i])
{
ans=std::min(ans,std::min(value[x][i],value[y][i]));
x=father[x][i];
y=father[y][i];
}
ans=std::min(ans,std::min(value[x][0],value[y][0]));
return ans;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
E.push_back((EDGE){u,v,w});
}
MaxTree();
for(int i=1;i<=n;i++)
{
if(!depth[i])
dfs(i,0,inf);
}
int Q;
scanf("%d",&Q);
while(Q--)
{
int x,y;
scanf("%d%d",&x,&y);
if(PointSet.SameSet(x,y))//是否连通
printf("%d\n",get_ans(x,y));
else
puts("-1");
}
return 0;
}