【GPLT】L2-025 分而治之

正文索引 [隐藏]

题目描述:

分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。

输入描述:

输入在第一行给出两个正整数 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;
}