CCCC L2-010. 排座位【并查集/分类讨论】
2024-10-21 02:56:35
L2-010. 排座位
时间限制
150 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。
输入格式:
输入第一行给出3个正整数:N(<= 100),即前来参宴的宾客总人数,则这些人从1到N编号;M为已知两两宾客之间的关系数;K为查询的条数。随后M行,每行给出一对宾客之间的关系,格式为:“宾客1 宾客2 关系”,其中“关系”为1表示是朋友,-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行,每行给出一对需要查询的宾客编号。
这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友,朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。
输出格式:
对每个查询输出一行结果:如果两位宾客之间是朋友,且没有敌对关系,则输出“No problem”;如果他们之间并不是朋友,但也不敌对,则输出“OK”;如果他们之间有敌对,然而也有共同的朋友,则输出“OK but...”;如果他们之间只有敌对关系,则输出“No way”。
输入样例:
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例:
No problem
OK
OK but...
No way
【分析】:
分类讨论:
1.有共同朋友+非敌对——>输出:No problem
2.无共同朋友+非敌对——>输出:OK
3.有共同朋友+敌对——>输出:OK but...
4.无共同朋友+敌对——>输出:No way
【代码】:
#include <bits/stdc++.h>
using namespace std;
#define N 250
int a[N][N],fa[N], n; void init(int n)
{
for(int i=; i<=N; i++){
fa[i] = i;
}
} int Find(int x)
{
//fa[x] == x ? fa[x] : Find(fa[x]);
while( x!= fa[x]){
x = fa[x];
}
return x; } void join(int x, int y)
{
int fx = Find(fa[x]);
int fy = Find(fa[y]);
if( fx != fy){
fa[fx] = fy;
}
} int main()
{
int n, m, k, f, x, y;
cin >> n >> m >>k; init(n); for(int i=; i<=m; i++)
{
cin >> x >> y >> f;
if(f==) join(x,y);
if(f==-) a[x][y] = a[y][x] = ;
} for(int i=; i<=k; i++){
cin >> x >> y;
if(Find(x)==Find(y) && a[x][y] == ) cout<<"No problem"<<endl;
if(Find(x)!=Find(y) && a[x][y] == ) cout<<"OK"<<endl;
if(Find(x)==Find(y) && a[x][y] == ) cout<<"OK but..."<<endl;
if(Find(x)!=Find(y) && a[x][y] == ) cout<<"No way"<<endl;
}
}
并查集
最新文章
- JSP模板继承功能实现
- How browsers work
- Hadoop step by step _ install and configuration environment
- sublime text2 css格式化插件
- python 抓取javascript 动态数据
- php用curl获取远端网页内容
- sqlserver 连不上的问题
- nofollow标签如何使用
- iOS开发网络资源整理-持续更新
- C#语法糖: 扩展方法(常用)
- 让自己的软件实现拖拽打开文件(使用WM_DROPFILES消息和DragQueryFile函数)
- Java序列化与反序列化,文件操作
- 解决jquery.zclip.js插件无法复制的问题
- java实现取球类的博弈问题
- 关于FFmpeg工具的使用总结
- [图形学] B样条曲线 - 原理和C++实现的演示程序(附源码)
- file常用功能
- html去掉滑动条
- Sql的行列(纵横表)转换
- 运行django新的项目,页面总是显示以前的项目,问题解决