1. P6121 [USACO16OPEN] Closing the Farm G
P3144 [USACO16OPEN] Closing the Farm S（逊版）
思路 \(\scr{Solution}\)
每一时刻关闭农场，求是否全联通。也就是维护将单个集合分成多个集合。
很容易想到爆搜算法，用 vector 邻接表建图，每次跑完图就将当前点的连边关系删去。复杂度 \(O(n^2)\)
只能拿 10pts ，居然有 WA qwq
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
int n, m;
bool vis[N];
vector<int> g[N];
void dfs(int fa, int x)
{
for (int i = 0; i < g[x].size(); i ++)
{
int y = g[x][i];
if (y == fa || vis[y]) continue;
vis[y] = true;
dfs(x, y);
}
}
void cut(int x)
{
for (int i = 0; i <g[x].size(); i ++)
g[x][i] = -1;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
while (n --)
{
memset(vis, false, sizeof(vis));
int x;
cin >> x;
vis[x] = true;
dfs(0, x);
bool flag = false;
for (int i = 1; i <= n; i ++)
if (!vis[i])
{
flag = true;
break;
}
cout << (flag ? "NO" : "YES") << '\n';
cut(x);
}
return 0;
}
正着搜不好优化，考虑倒过来思考。
即一开始所有农场都是关闭的，从后往前，判断每一时刻打开一个农场，对应正着想的当前状态下该农场还未关闭。
而正着想是判断当前状态下是否因关闭该农场而被分成了多个集合。
那倒着想就是打开多个农场，判断是否有多个集合（连通块）！
这不就是并查集了吗 ......
每次打开一个农场，默认多了一个集合，再通过图遍历直接相连的点是否打开了，打开了但又不在同一集合里就用并查集合并，同时抹去该单点集合。
每次操作完后就留下了当前状态下打开了的相连农场的集合数量。 done.
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N], fa[N], ans[N];
bool vis[N];
vector<int> g[N];
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) fa[i] = i;
int sum = 0;
for (int i = n; i >= 1; i --)
{
sum ++;
int k = a[i];
vis[k] = true;
for (int j = 0; j < g[k].size(); j ++)
{
int l = g[k][j];
if (find(k) != find(l) && vis[l])
{
merge(k, l);
sum --;
}
}
ans[i] = sum;
}
for (int i = 1; i <= n; i ++)
cout << (ans[i] == 1 ? "YES" : "NO") << '\n';
return 0;
}
总结 \(\scr{Summary}\)
- 有些题目正着想好做但常常不够优，所以当发现正着想超时时可以试着倒着思考；
- 一些分割性的问题可以转化为联通性的问题来做，从而考虑并查集；