P8403 [CCC2022 J4] Good Groups

题目背景

请注意：这道题是 CCO 2022 S2 Good Groups 的弱化版

管理备注：似乎没有弱化

题目描述

一个班级会被分成 g 个组，每个组有三个人，这种分组方式可能会违反两种规定：

1. 一些学生必须在同一小组；
2. 一些学生必须不在同一小组。

现在校长找到了你，问学生一共违反了多少个规定。

输入格式

第一行一个整数 x。紧接着 x 行，每行两个学生名字 name1​,name2​ ，表示这两个学生必须被分配到同一个小组。

接下来一个整数 y。紧接着 y 行，每行两个学生名字 name1​,name2​ ，表示这两个学生必须不在同一个小组。

接下来一个整数 g。紧接着 g 行，每行三个学生名字name1​,name2​,name3​，表示这三个学生现在被分在一个小组。

输出格式

输出一个整数，表示学生一共违反了多少个规定。

输入输出样例

输入 #1

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

输出 #1

0

输入 #2

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

输出 #2

3

说明/提示

样例2解释：

1. A 和 B 必须在同一组，这一点违反了。
2. G 和 L 必须在同一组，这一点违反了。
3. J 和 K 必须在同一组，这一点没有违反。
4. D 和 F 必须不在同一组，这一点违反了。
5. D 和 G 必须不在同一组，这一点没有被违反。

以上 5 条共违反 3 条，所以输出 3。

对于 25% 的数据：1≤g≤50,1≤x≤50,y=0

对于另外 60% 的数据：1≤g≤50,1≤x≤50,1≤y≤50

对于 100% 的数据：1≤g≤10^5,1≤x≤10^5,1≤y≤10^5

代码

#include<iostream>
#include<map>
using namespace std;
struct must_in{//定义必须在一组的人的名字
string name1,name2;
}m_i[100005];
struct must_not_in{定义必须不在一组的人的名字
string name1,name2;
}m_n_i[100005];
struct now{//定义已经分好的组
string name1,name2,name3;
}no[100005];
map<string,string>mp;//使用map映射函数
int main()
{
int x,y,g;
cin>>x;
for(int i=1;i<=x;i++){
cin>>m_i[i].name1>>m_i[i].name2;
}cin>>y;
for(int i=1;i<=y;i++){
cin>>m_n_i[i].name1>>m_n_i[i].name2;
}cin>>g;
for(int i=1;i<=g;i++){
cin>>no[i].name1>>no[i].name2>>no[i].name3;
mp[no[i].name1]=no[i].name1;//对于每个分组，让第一个名字的父节点指向自己
mp[no[i].name2]=no[i].name1;//对于每个分组，让第二个名字的父节点指向第一个名字
mp[no[i].name3]=no[i].name1;//对于每个分组，让第三个名字的父节点指向第一个名字
}
int cnt=0;//统计违反规定的组的数量
string xx,yy;
for(int i=1;i<=x;i++){
xx=mp[m_i[i].name1];//寻找第一个名字的父节点
yy=mp[m_i[i].name2];//寻找第二个名字的父节点
if(xx!=yy) cnt++;//判断是否违反规定
}
for(int i=1;i<=y;i++){
xx=mp[m_n_i[i].name1];//寻找第一个名字的父节点
yy=mp[m_n_i[i].name2];//寻找第二个名字的父节点
if(xx==yy) cnt++;//判断是否违反规定
}cout<<cnt;
return 0;
} 

原文地址：https://blog.csdn.net/m0_74387420/article/details/142730494

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！