算法搜索双向搜索
POJO双向搜索
定义
双向同时搜索的基本思路是从状态图上的起点和终点同时开始进行 广搜 或
深搜。
如果发现搜索的两端相遇了，那么可以认为是获得了可行解。
过程
双向广搜的步骤：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
从 q.front() 扩展出新的 s 个结点
如果 新扩展出的结点已经被其他数字标记过
那么 表示搜索的两端碰撞
那么 循环结束
如果 新的 s 个结点是从开始结点扩展来的
那么 将这个 s 个结点标记为 1 并且入队 q
如果 新的 s 个结点是从目标结点扩展来的
那么 将这个 s 个结点标记为 2 并且入队 q
}
|
题目描述
给出一张 个点 条边的无向图，每个点的初始状态都为
。
你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由
变成 或由 变成 。
你需要求出最少的操作次数，使得在所有操作完成之后所有 个点的状态都是 。
输入格式
第一行两个整数 。
之后 行，每行两个整数 ，表示在点 之间有一条边。
输出格式
一行一个整数，表示最少需要的操作次数。
本题保证有解。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
| 5 6
1 2
1 3
4 2
3 4
2 5
5 3
|
样例输出 #1
提示
对于 的数据，。保证没有重边和自环。
题解
- 考虑贪心，每个开关要么不用要么按一次。
- 需要用二进制来进行表示哪个状态使用过，哪个没有使用过。
- 最后是匹配是使用二进制 ^ 匹配前 的状态。
- 具体实现时，可以把前半段的状态以及达到每种状态的最少按开关次数存储在
map
里面，搜索后半段时，每搜出一种方案，就把它与互补的第一段方案合并来更新答案。
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
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
a[0] = 1;
for(int i = 1; i < n; i ++ ) {
a[i] = a[i - 1] * 2;
}
for(int i = 1; i <= m; i ++ ) {
int u, v; cin >> u >> v;
--u, --v;
a[u] |= ((long long)1 << v);
a[v] |= ((long long)1 << u);
}
for (int i = 0; i < (1 << (n / 2)); ++i) {
long long t = 0;
int cnt = 0;
for (int j = 0; j < n / 2; ++j) {
if ((i >> j) & 1) {
t ^= a[j];
++cnt;
}
}
if (!f.count(t))
f[t] = cnt;
else
f[t] = min(f[t], cnt);
}
for (int i = 0; i < (1 << (n - n / 2)); ++i) {
long long t = 0;
int cnt = 0;
for (int j = 0; j < (n - n / 2); ++j) {
if ((i >> j) & 1) {
t ^= a[n / 2 + j];
++cnt;
}
}
if (f.count((((long long)1 << n) - 1) ^ t))
ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
}
cout << ans;
return 0;
}
|
