某军搞信息对抗实战演习,红军成功地侵入了蓝军的内部网络,蓝军共有两个信息中心,红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息,但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快地解决这个问题,应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?
链接🔗
[ZJOI 2004] 嗅探器
题解
简化题意
给一张无向图,求图上两点路径的字典序最小的割点
s
为起点,t
为终点,x
为当前枚举到的割点,从s
点开始进行tarjan
- 割点不在起点或者终点
dfn[t] > dfn[x]
, 因为终点绝对在当前点后面被枚举到low[t] >= dfn[x]
,确保x
点在路径上
- 因为如果
low[t]
没被枚举到时,它的值为0
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5;
struct {
int v, net;
} e[maxd << 1];
int f[maxd], eid;
void insert(int x, int y) {
e[eid].v = y;
e[eid].net = f[x];
f[x] = eid++;
}
void init() {
memset(f, -1, sizeof(f));
eid = 0;
}
int dfn[maxd], low[maxd], tot = 0, n, s, t, ans = 1e9;
void tarjan(int x) {
dfn[x] = low[x] = ++tot;
for (int i = f[x]; i + 1; i = e[i].net) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[v], low[x]);
if (dfn[x] <= low[v] && x != s && x != t && dfn[t] >= dfn[v] && low[t] >= low[x])
ans = min(ans, x);
}
low[x] = min(low[x], dfn[v]);
}
}
int main() {
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
int a, b;
init();
scanf("%d", &n);
while (1) {
scanf("%d %d", &a, &b);
if (a == 0 || b == 0)
break;
insert(a, b);
insert(b, a);
}
scanf("%d %d", &s, &t);
tarjan(s);
if (ans != 1e9)
printf("%d\n", ans);
else
printf("No solution");
return 0;
}