F-鸡玩炸蛋人_2023牛客寒假算法基础集训营1 (nowcoder.com)
炸鸡最近在 ɔiq彐 平台上白嫖了一款游戏：《炸蛋人》。
《炸蛋人》的主角炸蛋人生活在一张n个结点（编号1到n）m条边的无向图上（图不一定联通），炸鸡可以控制炸蛋人进行两种操作：移动和放置炸蛋。具体说明如下。
移动：炸蛋人可以移动到当前所在结点通过一条边相连的相邻节点，但炸蛋人只能移动到没有炸蛋的结点。注意，尽管不能移动到有炸蛋的结点，但允许炸蛋人从一个当前有炸蛋的结点出发，移动到相邻没有炸蛋的结点。
放置炸蛋：炸蛋人在当前位置放置一枚炸蛋，炸蛋一经放置就会永久存在于图中（炸蛋全称为炸制金黄色的农家土鸡蛋，因此当然不会爆炸），每个位置可以放置多枚炸蛋。
已知炸蛋人所在的无向图初始没有炸蛋，炸蛋人出现在了地图上的S点，炸鸡对炸蛋人进行了一系列的操作，炸蛋人最终停留在了T点。现在，给出无向图最终的情况，请你求出有多少种可能的起点终点方案(S,T)，两种方案不同当且仅当它们的起点和终点至少有一个不同。若无合法方案输出0。
输入第一行包括两个整数，表示无向图的结点个数和边的个数。
接下来行，每行两个正整数表示之间有一条边，可能有自环或重边。
最后一行包括个正整数，第个正整数表示号结点上最终有多少个炸蛋。
输出一个正整数，表示题目所求的的对儿数，若无合法的方案输出。
输入
6 4
1 2
2 3
1 3
4 6
0 0 0 0 0 0输出
14思路
题意大概为, 在一个无向图内, 任意选择一个起点S, 一个终点T, 若从S点出发能到达T, 则成立。求所有成立的方案数, 两种方案不同当且仅当它们的起点S和终点T有一个不同。
此时可以想到, 在一个连通块内（每个点都可以到达另一个点）, 其起点和终点的方案数就是连通块大小（点个数） 所有点的组合数, ST可以相同。一个求连通块问题, 直接并查集/DFS即可。
第一个样例即可证明该推测正确, 三个连通块, 大小分别为 , 那么最终答案就是
不过还有一个要求, 需要保证在所有方案走完后, 对应点放足够的炸弹。加上炸弹的约束后, 引出两个操作：
- 移动到没有炸弹的节点
- 在当前位置放置一个炸弹, 可以放置多个, 当前S-T方案中放置后对以后的S-T方案也存在。
假如只需要在一个点上放炸弹（放多少都一样）, 即样例2：
显然, 对于所有的S-T, 唯一能满足放完后在点5上有两个炸弹的方案只有一种：
从5开始走, 连续放俩炸弹, 然后在5结束。
那如果这个点在第一个连通块内呢？比如1号点：
- 从1号点开始 S=1, 可以直接放置炸弹然后去其他点, 共3种方案
- 从2号点开始 S=2, 共 3 种方案
- 对于T=1, 直接走到1号点然后放置炸弹即可
- 对于T=2, 先走到1号点放置炸弹, 然后再走回2号点
- 对于T=3, 同理
- 从3号点开始 S=3, 也是 3 种方案。
可以发现, 有炸弹和没炸弹, 在该连通块内对结果是没有影响的。那么对于多个点有炸弹也成立么？假设1,2号点都有2个炸弹：
- 从1号点开始 S=1
- 对于T=1, 先走到2号点放炸弹, 然后走回1号点放炸弹
- 对于T=2, 先在1号点放炸弹, 然后走2号点放炸弹
- 对于T=3, 先在1号点放炸弹, 然后走2号点放炸弹, 最后走3号点 继续推可以发现依然成立。
故可以归纳推理得出性质：一个连通块内的方案数无论有没有炸弹, 都是连通块大小的平方, 即。 从另一个角度证明：对于一条S-T的路径, 且此路径经过所有该放炸弹的点, 只需要在从A点走到B点前, 在A点放炸弹即可。也可以将该路径看做从T点DFS搜到S点的一条路径, 到达S点后开始一直返回, 在回溯时将该点放置炸弹。 因此该性质成立。
答案也很好求了, 如果两个炸弹所在点不在一连通块内, 即两点不存在通路, 则无解, 不可能存在一个S-T路径, 是的两个点都放炸弹。若只有一个连通块内有炸弹, 则答案就是该连通块大小的平方。若都没有炸弹, 那就是所有连通块大小的平方和。
代码
// jiangly 大佬的代码
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return leader(x) == leader(y); }
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[leader(x)]; }
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
DSU dsu(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
dsu.merge(u, v);
}
int comp = 0;
std::vector<int> s(n);
for (int i = 0; i < n; i++) {
int c;
std::cin >> c;
if (c) {
int x = dsu.leader(i);
comp += !s[x];
s[x] += c;
}
}
i64 ans = 0;
for (int i = 0; i < n; i++) {
if (dsu.leader(i) == i) {
if (comp - (s[i] > 0) == 0) {
int s = dsu.size(i);
ans += 1LL * s * s;
}
}
}
std::cout << ans << "\n";
return 0;
}