当前位置:网站首页>F - True Liars (种类并查集+DP)
F - True Liars (种类并查集+DP)
2022-07-06 06:08:00 【RCyyds】
传送门: True Liars
题意:给出n对关系,p1个好人,p2个坏人。要求根据n对关系中找出好人有哪些,若方案唯一,则逐个输出好人,最后输出end;若方案不唯一/找不到,那么输出no
思路:第一次碰到这种类型的题目,想了很久没什么思路,参考了其他人的博客才弄懂了。
以下为所参考博客的思路:
通过简单的分析可以得出,对于每对关系(x,y,yes/no),若关系为yes,则x和y属于同一类人;若关系为no,则x和y属于相反类人。
根据初步的n对关系,我们只可以推出哪些属于同一类人,哪些属于相反类人,但不可以确定到底哪类是好人/坏人。我们可以将相反的两类人确定为一个大集合,那么大集合里面就有两个小集合。根据题意,我们只需要从每个大集合中,选其中一个小集合,使得选中的所有小集合的人数总和为p1即可。
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 600
using namespace std;
int parent[MAXN], path[MAXN][MAXN], dp[MAXN][MAXN];
int num[MAXN]; //记录大集合的根节点为i的是第num[i]个大集合
int flag[MAXN][2]; //标记每个大集合中选中到最终结果的小集合
int cnt[MAXN][2]; //根节点为i时,分别记录两个小集合包含的人数
int relat[MAXN];
/* relation
* relat=0/1。0表示i和根节点parent[i]相关联,即属于同一个小集合;1表示i和根节点不关联,即属于同一个大集合中的不同小集合*/
int find(int x) {
if (x != parent[x]) { //此处的parent[x]是旧父
int px = find(parent[x]); // px是新父
relat[x] ^= relat[parent[x]];
/* 由于路径压缩要将x的父亲节点直接指向根节点,即更改了x的父亲节点,所以要更新节点x和根节点的关系。
*/
parent[x] = px;
}
return parent[x];
}
/*
对于"relat[x] ^= relat[parent[x]];"异或解释:
可以通过简单的分析得出:
1.如果( relation[x和旧父]=0 && relation[旧父和新父]=0 )或者(
relation[x和旧父]=1 && relation[旧父和新父]=1 ),则 relation[x和新父]=0
2.如果(relation[x和旧父]=1 && relation[旧父和新父]=0 )或者(
relation[x和旧父]=0 && relation[旧父和新父]=1 ),则 relation[x和新父]=1
可以发现,最终relatino[x和新父] = relation[x和旧父] ^ relation[旧父和新父]
即: relat[x] ^= relat[parent[x]];
对于下面的merge函数中的异或同理
*/
void merge(int x, int y, int d) { // d要么为0,要么为1
int px = find(x);
int py = find(y);
if (px != py) {
parent[py] = px;
relat[py] = relat[x] ^ relat[y] ^ d;
}
}
int main(void) {
int m, p, q;
while (scanf("%d%d%d", &m, &p, &q)) {
if (m + p + q == 0) {
break;
}
for (int i = 1; i <= p + q; i++) { //**初始话
relat[i] = 0;
parent[i] = i;
}
while (m--) {
int x, y, d = 1;
char ch[5];
scanf("%d%d%s", &x, &y, ch);
if (ch[0] == 'y') {
d = 0;
}
merge(x, y, d);
}
memset(num, 0, sizeof(num)); //**num存储集合个数并且给他们编号
memset(path, 0, sizeof(path));
memset(cnt, 0, sizeof(cnt));
memset(dp, 0, sizeof(dp));
memset(flag, 0, sizeof(flag));
int tot = 0;
for (int i = 1; i <= p + q; i++) { //**统计集合个数并且编号
if (find(i) == i) {
num[i] = ++tot; // tot连通块个数,num记录root=i的连通块的编号
}
}
for (int i = 1; i <= p + q;
i++) { //**分别统计每个集合两种类的数目并存储到cnt中
cnt[num[find(i)]][relat[i]]++;
}
dp[0][0] = 1;
for (int i = 1; i <= tot; i++) { // tot=2
for (int j = 0; j <= p+q; j++) { // p+q=7
//**dp[i][j]存储到第i个集合选择种类和为j的方法数
if (j - cnt[i][0] >= 0 && dp[i - 1][j - cnt[i][0]]) {
dp[i][j] += dp[i - 1][j - cnt[i][0]];
path[i][j] =
cnt[i][0]; //**path数组记录路径,即选的是1还是0
}
if (j - cnt[i][1] >= 0 && dp[i - 1][j - cnt[i][1]]) {
dp[i][j] += dp[i - 1][j - cnt[i][1]];
path[i][j] = cnt[i][1];
}
}
}
/*
这部分两个if有点难理解,因为可能会想到,两个if都满足的话,那么最后得出的dp[i][j]就有可能存在同一个大集合里面选取了两个小集合的情况,这样就违背了“只从一个大集合选其中一个小集合”的情况。但,可以发现,我们最后限制了方法数是dp[tot][p]=1时,才是有唯一方案的。如果像刚刚说的两个if都满足,那么dp[i][j]一定>1,也就不会符合下面的dp[tot][p]=1限制,所以解决了这个问题。
*/
if (dp[tot][p] != 1) {
printf("no\n");
} else {
for (int i = tot, j = p; j > 0 && i > 0; i--) { //**标记路径
if (path[i][j] == cnt[i][0]) {
flag[i][0] = 1;
} else {
flag[i][1] = 1;
}
j -= path[i][j];
//记得减。因为背包时恰好选够p,所以要跟随着p逐次减少当时的物品,找到路径
}
for (int i = 1; i <= p + q; i++) {
if (flag[num[find(i)]][relat[i]]) {
printf("%d\n", i);
}
}
printf("end\n");
}
}
return 0;
}
边栏推荐
- 《卓有成效的管理者》读书笔记
- Dynamic programming -- knapsack problem
- 还在为如何编写Web自动化测试用例而烦恼嘛?资深测试工程师手把手教你Selenium 测试用例编写
- A complete collection of necessary learning websites for office programmers
- [Thesis code] SML part code reading
- IDEA 新UI使用
- 多线程应用的测试与调试
- [postman] collections - run the imported data file of the configuration
- Usage of test macro of GTEST
- Bit operation rules
猜你喜欢
Significance of unit testing
J'ai un chaton.
Coordinatorlayout+nestedscrollview+recyclerview pull up the bottom display is incomplete
全程实现单点登录功能和请求被取消报错“cancelToken“ of undefined的解决方法
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
IP day 16 VLAN MPLS configuration
What are the test sites for tunnel engineering?
Wib3.0 leapfrogging, in leapfrogging (ง • ̀_•́) ง
Pat (Grade B) 2022 summer exam
Buuctf-[[gwctf 2019] I have a database (xiaoyute detailed explanation)
随机推荐
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Thoughts on data security (Reprint)
10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
[C language] qsort function
对数据安全的思考(转载)
请求转发与重定向
P问题、NP问题、NPC问题、NP-hard问题详解
【C语言】qsort函数
[postman] collections - run the imported data file of the configuration
假设检验学习笔记
Introduction to promql of # yyds dry goods inventory # Prometheus
Interface test: what are the components of the URL in fiddler
Buuctf-[[gwctf 2019] I have a database (xiaoyute detailed explanation)
多线程应用的测试与调试
功能安全之故障(fault),错误(error),失效(failure)
ContentType的作用
职场进阶指南:大厂人必看书籍推荐
Idea new UI usage
H3C S5820V2_ Upgrade method after stacking IRF2 of 5830v2 switch
LAN communication process in the same network segment