令人智熄的二分操作

AC记录

要看正常的解法请看其他题解

而且还蛮快的。。。

其实,这是非常奇葩的一个想法

总体思路就是:二分答案

你没听错,二分答案

我们从题面中可以看到,其实这道题的拥挤度也就$10000$而已,所以我们就会发现二分似乎可以???

存图存完之后直接二分,二分的$Check()$里面打一个$BFS$,来求能否通往终点,就好了

具体的东西就上代码来看吧


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
#include<bits/stdc++.h> // 万能头文件 

using namespace std;

// 邻接表存图
// 由于是无向图,所以这些数组要开大一倍,我就是这么被坑掉了10分
int End[50100]; // End[i]表示第i条边的终点
int Value[50100]; // Value[i]表示第i条边的边权
int Next[50100]; // Next[i]表示第i条边的下一条边
int Head[10100]; // Head[i]表示第i个点的第一条便

int q[50100]; // BFS的队列
int n, m, s, t; // 如题意
int qf, qe; // BFS队列的队首、队尾
bool Used[10100]; // BFS,表示是否到过这个点

bool Check(int x){
memset(Used, false, sizeof(Used)); // 朴实无华的BFS
qf = qe = 1;
q[1] = s;
Used[s] = true;
while(qf <= qe){
int xx = Head[q[qf]];
while(xx != -1){
if(!Used[End[xx]] && Value[xx] <= x){ // 拓展
q[++qe] = End[xx];
Used[End[xx]] = true;
}
xx = Next[xx];
}
qf++; // 出队
}
return Used[t]; // 返回终点有没有到过
}

int main(){
memset(Next, -1, sizeof(Next));
memset(Head, -1, sizeof(Head));
scanf("%d %d %d %d", &n, &m, &s, &t);
int r = 0;
for(int i = 1; i <= m; i++){ // 读入、存图
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
Value[i*2] = c;
End[i*2] = b;
Next[i*2] = Head[a];
Head[a] = i*2;
Value[i*2+1] = c; // 由于是无向图,所以要存两次
End[i*2+1] = a;
Next[i*2+1] = Head[b];
Head[b] = i*2+1;
if(c > r)
r = c; // 生成一个值等于所有最高拥挤度的r,方便二分
}
// ------------读入完毕---------------
// ------------二分开始---------------
r++;
int l = 1;
while(l < r){ // 同样朴素的二分~~~
int Mid = ((l+r) >> 1);
if(Check(Mid))
r = Mid;
else l = Mid+1;
}
printf("%d", l);
}

感谢 学委 对我的启发

 评论