【洛谷】题解 CF1277E【Two Fairs】
题目大意
给出一张无向图以及两个点 a,b ，之后您需要求出有多少对点对 (u,v) 满足从 u 到 v 的任意一条路径都必须同时经过点 a,b 。
同时若 (u,v) 中的任何一个点为 a 或 b ，则这个点对也不合法。
n <= 1e5
吐槽
虽然确实挺有意思，但是这么简单的题，出到 Div2E 我觉得有点不合适吧QAQ。
另外这一篇题解中您可能会大量看见某些词的重复使用。
题解
我们从 a 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 b 。
之后从 b 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 a 。
此时我们应当有三类点：只被 a 染色、只被 b 染色、同时被 a,b 染色，由于图是联通的，所以不会存在没有被染色的点。
答案是第一类点的数量乘上第二类点的数量。
证明
我们考虑一对合法的点 (u,v) ，为方便起见我们假设 u 是第一类点而 v 是第二类点。之后我们思考一下 u 只被 a 染色的意义是什么。
实际上这意味着 u 可以通过某些方式到达 a ，但它不能通过 a 以外的任何点到达 b ，换句话而言若 u 想有一条到 b 的路径，那么其路径上必须经过 a 。
实际上 v 只被 b 染色的意义是相似的。
之后我们想证明什么？ 我们想证明任何一条从 u 到 v 的路径都必须经过 a,b 。
我们讨论一下一条从 u 到 v 的路径的情况。
实际上我们只需要考虑一下是否可以存在不同时经过 a,b 的路径的可能性就好了。
具体来说，我们假设存在一条路径使得其不经过 b ，那么应当有：
从 v 能不经过 b 到达 u 。
u 能不经过 b 到达 a 。
从 v 能不经过 b 到达 a
于是我们发现此时出现了矛盾，第二类点实际上是不能通过 b 以外的点到达 a 的，于是不可能存在这样一条路径。
证明不存在一条路径使其不经过 a 也可以用相同的方法证明出来。
于是我们就证明了至少有这么多点对是可行的。
之后我们还需要证明其他的点对是不可行的。。
实际上这里的证明和上面的证明也是相似的所以略过。
然后就把这个做法的正确性证明出来了~
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int_t;
char getch()
{
static char buf[100000], *s, *t;
return (s == t) && (t = (s = buf) + fread(buf, 1, 100000, stdin)), s == t ? EOF : *s++;
}
#ifdef local
#define getch getchar
#endif
int_t read()
{
int_t x = 0, w = 1;
char ch = 0;
while (!isdigit(ch))
{
ch = getch();
if (ch == '-')
w = -1;
}
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getch();
return x * w;
}
vector<int_t> G[200010];
int_t color[200010];
void bfs(int_t a, int_t b, int_t col)
{
queue<int_t> que;
que.push(a);
while (!que.empty())
{
int_t rt = que.front();
que.pop();
color[rt] |= col;
if (rt != b)
for (int_t to : G[rt])
if (!(color[to] & col))
que.push(to);
}
}
int main()
{
int_t T = read();
while (T--)
{
int_t n = read(), m = read(), a = read(), b = read();
for (int_t i = 1; i <= n; i++)
G[i].clear(), color[i] = 0;
while (m--)
{
int_t u = read(), v = read();
G[u].push_back(v);
G[v].push_back(u);
}
bfs(a, b, 1);
bfs(b, a, 2);
int_t ans1 = 0, ans2 = 0;
for (int_t i = 1; i <= n; i++)
if (color[i] == 1)
ans1++;
else if (color[i] == 2)
ans2++;
cout << ans1 * ans2 << endl;
}
}
评论
发表评论