当前位置:网站首页>【练习-6】(PTA)分而治之
【练习-6】(PTA)分而治之
2022-07-06 09:26:00 【火焰车】
题目:
分而治之 (25 分)
分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。
输入格式:
输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (≤ 100)和随后的 K 行方案,每行按以下格式给出:
Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量,后面的系列 v[i] 是计划攻下的城市编号。
输出格式:
对每一套方案,如果可行就输出YES,否则输出NO。
输入样例:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出样例:
NO
YES
YES
NO
NO
第一眼以为这是一道并查集的题,再一看好像不是那么一回事儿。
本题就是输出删除了几个位置之后,剩下的点还有没有与其他的点相连,如果没有(相对独立,孤立无援)就输出“YES” 否则输出NO。
例如:
1 2 相通 2 3相通,如果删除2的话只剩下1 3是不相通的输出“YES",而如果删除1的话 2 3仍然是相通的不符合孤立无援,所以输出”NO“
知道了这些,其实也不是很难了。
CODE:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int x,y;
}a[10005];
int k[10005];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y;
int ww;
cin>>ww;
for(int i=1;i<=ww;i++)
{
int q,x;
cin>>q;
for(int j=1;j<=q;j++)
{
cin>>x;
k[x] = 1;
}
int f = 1;
for(int j=1;j<=m;j++)
{
if(k[a[j].x]==0 && k[a[j].y]==0)
{
cout<<"NO"<<endl;
f = 0;
break;
}
}
if(f)
cout<<"YES"<<endl;
}
return 0;
}
代码分析:
记录下每一条边(应该也可以用pair),两点就代表一条线。
然后对某个点进行标记,如果这个点要被删除那么就k[x] = 1。这样的话,一条边上两个点只要有一个点被删除,这条边就不存在了,也就是说我们只要判断每条边的两个点有没有被删除(一个或两个)即可。如果有某条边两个点都没有被删除,那么就要输出“NO”;
边栏推荐
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- JS调用摄像头
- STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
- Opencv learning log 16 paperclip count
- 0-1 knapsack problem (I)
- Cost accounting [17]
- Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
- Medical colposcope Industry Research Report - market status analysis and development prospect forecast
- Path problem before dynamic planning
- Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
猜你喜欢
Learning record: STM32F103 clock system overview working principle
Matlab comprehensive exercise: application in signal and system
JS --- all basic knowledge of JS (I)
学习记录:理解 SysTick系统定时器,编写延时函数
ucorelab3
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
STM32學習記錄:輸入捕獲應用
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
B - 代码派对(女生赛)
学习记录:TIM—基本定时器
随机推荐
Opencv learning log 12 binarization of Otsu method
Cost accounting [18]
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
编程到底难在哪里?
学习记录:STM32F103 时钟系统概述工作原理
UCORE Lab 1 system software startup process
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
Opencv learning log 15 count the number of solder joints and output
Alice and Bob (2021牛客暑期多校训练营1)
【练习-8】(Uva 246)10-20-30==模拟
China potato slicer market trend report, technical dynamic innovation and market forecast
差分(一维,二维,三维) 蓝桥杯三体攻击
Learning record: USART serial communication
China medical check valve market trend report, technical dynamic innovation and market forecast
Research Report on market supply and demand and strategy of China's Medical Automation Industry
【练习-10】 Unread Messages(未读消息)
Opencv learning log 33 Gaussian mean filtering
Research Report on market supply and demand and strategy of China's land incineration plant industry
力扣刷题记录--完全背包问题(一)