【GPLT】L2-025 分而治之
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88871494
题目描述：
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入描述：
输入在第一行给出两个正整数 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解题思路：
我一开始用bool型二维数组Edge来存储相邻的城市信息，用set来记录被攻陷的城市信息，用isLonely来判断是不是所有的城市都被孤立，当一个没被攻陷的城市与另一个没被攻陷的城市相邻时，标记isLonely为false 表明并不是所有的城市都被孤立了。然而提交代码之后25分只得了15分，测试点3、4出现了段错误。这就很难受了，我define了一个MAX 10005，令二维数组Edge的大小为MAX，提交之后所有测试点都出现了段错误，这就说明段错误是二维数组导致的。学姐说把二维数组改掉，换成vector来记录相邻城市信息，然后提交代码之后AC啦。set.count(X)==0和set.find(X)==set.end()的作用是一样的嗷，都是用来判断set中有无X的。
AC代码：段错误代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,M; //敌方城市个数N,通路条数M
cin >> N >> M;
bool Edge[N+1][N+1];
memset(Edge,false,sizeof(Edge)); //初始化
for(int i = 0; i < M; i++)
{
int x,y;
cin >> x >> y;
Edge[x][y] = Edge[y][x] = true;
}
int K; //K个方案
cin >> K;
while(K--)
{
bool isLonely = true; //判断是不是所有的城市都被孤立了
int Np; //某方案计划攻下的城市数量Np
cin >> Np;
set<int> s; //用来记录被攻下的城市
for(int i = 0; i < Np; i++)
{
int temp;
cin >> temp;
s.insert(temp);
}
for(int i = 1; i <= N; i++)
{
if(s.count(i) == 0) //若还有没被攻陷的城市
{
for(int j = 1; j <= N; j++)
{
if(Edge[i][j] && s.count(j) == 0) //存在一个相邻的没被攻陷的城市,说明没有孤立
{
isLonely = false;
}
}
}
}
if(isLonely)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,M; //敌方城市个数N,通路条数M
cin >> N >> M;
vector<int> v[N+1];
for(int i = 0; i < M; i++)
{
int x,y;
cin >> x >> y;
v[x].push_back(y); //表示x和y是相邻城市
}
int K; //K个方案
cin >> K;
while(K--)
{
bool isLonely = true; //判断是不是所有的城市都被孤立了
int Np; //某方案计划攻下的城市数量Np
cin >> Np;
set<int> s; //用来记录被攻下的城市
for(int i = 0; i < Np; i++)
{
int temp;
cin >> temp;
s.insert(temp);
}
for(int i = 1; i <= N; i++)
{
if(s.find(i) == s.end()) //若还有没被攻陷的城市
{
for(int j = 0; j < v[i].size(); j++)
{
if(s.find(v[i][j]) == s.end()) //若这个没被攻陷的城市还有相邻的未被攻陷的城市
{
isLonely=false;
}
}
}
}
if(isLonely)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}腾讯云开发者
