题目描述
blablabla
样例
blablabla
算法1
(并查集+dp+路径还原)
前置知识 并查集(食物链 那道题要会做),dp的路径还原(可以状态回溯)
1.对于 a b yes, 我们合并(a,b)和(a + p1 + p2, b + p1 + p2)
代表a,b一体,如果a是好人则b是好人,如果a(a + p1 + p2)是坏人,则b(b + p1 + p2)是坏人
2.对于 a b no, 合并(a, b + p1 + p2), (a + p1 + p2, b)含义和上面一样
仅有人之间的指认关系是不知道答案的,我们要找几个集合,恰好且仅有一种方法能凑出 p1 人才有答案
对于每个人,要么是好人,要么是坏人(废话,下面是关键)
所以对于每个人,
1.这个人 i 所在的集合全是好人,与 i + p1 + p2 处于一个集合的都是坏人
即father[其他人] == father[i] 的 都是好人, father[其他人] == father[i + p1 + p2] 的 都是坏人
2. 这个人 i 是坏人,………………
每个大集合分为,这个集合的father是好人, father是坏人
所以dp的时候必须从上个状态转移(不存在这个人及不是好人也不是坏人在状态转换)不能直接继承
对于前i个集合可拼成 j个好人, 转移:
dp[i][j] += dp[i - 1][j - 集合的father是好人时好人人数]
dp[i][j] += dp[i - 1][j - 集合的father是坏人时好人人数]
dp[i][j] 存的是能满足前i个集合可拼成 j个好人的方法数,只有当(dp[集合个数][p1] == 1)能唯一确定谁是好人,谁是坏人
dp状态的回溯见代码,毕竟 (dp[集合个数][p1] == 1) 路径是唯一的很简单
C++ 代码
放一个简短的代码, 原代码在最下面
#include <bits/stdc++.h>
using namespace std;
const int N = 605;
int f[N << 1], sz[N << 1], n, p1, p2;
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void unit(int x, int y) { x = find(x), y = find(y); if (x ^ y) f[y] = x, sz[x] += sz[y]; }
int main() {
while (cin >> n >> p1 >> p2, n || p1 || p2) {
bool g = 0;
for (int i = 1; i <= p1 + p2; ++i) f[i] = i, f[i + p1 + p2] = i + p1 + p2, sz[i] = 1, sz[i + p1 + p2] = 0;
for (int i = 0; i < n; ++i) {
int x, y; char s[5]; cin >> x >> y >> s;
if (s[0] == 'n')
if (find(x) == find(y)) g = 1;
else unit(x, y + p1 + p2), unit(x + p1 + p2, y);
else
if (find(x) == find(y + p1 + p2)) g = 1;
else unit(x, y), unit(x + p1 + p2, y + p1 + p2);
}
vector<pair<int, pair<int, int>>> a(1); vector<unordered_set<int>> st(1); st[0].insert(0);
for (int i = 1; i <= p1 + p2; ++i) if (f[i] == i) {
a.push_back({ i, {sz[i], sz[find(i + p1 + p2)]} }); st.push_back(unordered_set<int>());
for (auto b : st[st.size() - 2]) st.back().insert(b + sz[i]), st.back().insert(b + sz[find(i + p1 + p2)]);
}
unordered_set<int> ans;
for (int i = a.size() - 1, res = p1; i; --i)
if (st[i - 1].count(res - a[i].second.first) && st[i - 1].count(res - a[i].second.second)) { g = 1; break; }
else if (st[i - 1].count(res - a[i].second.first)) ans.insert(a[i].first), res -= a[i].second.first;
else ans.insert(a[i].first + p1 + p2), res -= a[i].second.second;
if (!st.back().count(p1) || g) { cout << "no\n"; continue; }
for (int i = 1; i <= p1 + p2; ++i) if (ans.count(find(i))) cout << i << '\n'; cout << "end\n";
}
return 0;
}
原代码
#include <bits/stdc++.h>
using namespace std;
int f[1205], s[1205], n, x, y, sum, h[1205];
int tot, a[605], vis[1205], b[605], dp[605][605];
char str[5];
int find(int x)
{
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
void unit(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
if (h[x] > h[y]) s[x] += s[y], f[y] = x;
else if (h[x] < h[y]) s[y] += s[x], f[x] = y;
else s[x] += s[y], f[y] = x, ++ h[x];
}
void init()
{
memset(dp, 0, sizeof dp);
sum = x + y, tot = 0, dp[0][0] = 1;
for (int i = 1; i<= sum; ++ i)
{
f[i] = i, f[i + sum] = i + sum;
s[i] = h[i] = h[i + sum] = 1;
s[i + sum] = vis[i] = vis[i + sum] = 0;
}
}
int main()
{
while(scanf("%d%d%d", &n, &x, &y), n + x + y)
{
init();
for (int i = 1, a, b; i <= n; ++ i)
{
scanf("%d%d%s", &a, &b, str + 1);
if (str[1] == 'y') unit(a, b), unit(a + sum, b + sum);
else unit(a, b + sum), unit(a + sum, b);
}
for (int i = 1, fi; i<= sum; ++ i)
{
if((fi = find(i)) != i) continue;
vis[fi] = vis[fi + sum] = ++ tot;
a[tot] = s[fi], b[tot] = s[fi + sum];
}
for (int i = 1; i <= tot; ++ i)
{
for (int j = min(a[i], b[i]); j <= x; ++ j)
{
if (j >= a[i]) dp[i][j] += dp[i - 1][j - a[i]];
if (j >= b[i]) dp[i][j] += dp[i - 1][j - b[i]];
}
}
if (dp[tot][x] != 1) {puts("no"); continue;}
for (int i = tot; i; -- i)
if (dp[i - 1][x - a[i]]) x -= a[i], a[i] = -1;
else if (dp[i - 1][x - b[i]]) x -= b[i], a[i] = -2;
for (int i = 1, fi = find(1); i <= sum; fi = find(++ i))
if(vis[fi])
if (fi > sum && a[vis[fi]] == -2) printf("%d\n", i);
else if (fi <= sum && a[vis[fi]] == -1) printf("%d\n", i);
puts("end");
}
return 0;
}
大佬,请问为什么s[i + sum]需要初始化为0?
因为要用到x+p1+p2
似乎h数组的按秩合并没用啊(
大佬,请问h数组是干什么的,是按秩合并吗?
是的