【LuoguP5145】漂浮的鸭子
题目链接: https://www.luogu.org/problemnew/show/P5145
前言
最近颓的东西太多了, 终于又来做搜索题.
这题很水 随手交了个暴力随机化就A了.
分析
这道题正解思路非常妙, 代码比较短. 但我们能不能想一个更简单粗暴的方法呢?
先交一下能被卡成接近 $ O(n^2) $ 的暴力, 对于每一个点跑一遍DFS, 如果能回到此点就更新答案, 再加一个玄学剪枝, 将这个环上所有点打标记, 这些点就不用再DFS了.
开O2只有50分
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
|
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n, tox[100001], toy[100001], rex[100001], tmpx, ans, walkpast[100001], lw[100001];
void dfs(int nown) {
memcpy(walkpast, lw, sizeof(walkpast));
int sum= 0, to= nown;
while(!walkpast[to]) {
walkpast[to]= 1;
sum+= toy[to], to= tox[to];
}
if(to != nown) return;
memcpy(lw, walkpast, sizeof(walkpast));
ans= max(ans, sum);
return;
}
int main() {
cin >> n;
for(int i= 1; i <= n; i++) cin >> tox[i] >> toy[i], rex[tox[i]]= i;
for(int i= 1; i <= n; i++)
if(!walkpast[i]) dfs(i);
cout << ans << endl;
return 0;
}
|
考虑优化, 其实复杂度是可以玄学过去的 先把cin换成scnaf.
然后我加了判断有环, 但此点不在环上的一个小剪枝.
1
2
3
4
| if(to != nown) {
lw[nown]= 1;
return;
}
|
通俗一点讲, 让以后到达这个点的鸭子都知道自己的水坑不在环里就不用继续搜了.
要是还T怎么办, 那改一下搜索顺序说不定就A了, 为了防止从 N 到 1 一条链卡暴力的情况, 我选择随机起点, 再加一个卡时限.
代码
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
| #include <iostream>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
using namespace std;
int n, tox[100001], toy[100001], rex[100001], tmpx, ans, walkpast[100001], lw[100001];
void dfs(int nown) {
memcpy(walkpast, lw, sizeof(walkpast));
int sum= 0, to= nown;
while(!walkpast[to]) {
walkpast[to]= 1;
sum+= toy[to], to= tox[to];
}
if(to != nown) {
lw[nown]= 1;
return;
}
memcpy(lw, walkpast, sizeof(walkpast));
ans= max(ans, sum);
return;
}
int main() {
scanf("%d", &n);
for(int i= 1; i <= n; i++) scanf("%d%d", tox + i, toy + i), rex[tox[i]]= i;
while(clock() < CLOCKS_PER_SEC * 0.9) {
int tmpx= rand() % n + 1;
if(!walkpast[tmpx]) dfs(tmpx);
}
printf("%d\n", ans);
return 0;
}
|
