P5030 长脖子鹿放置

    • 265通过
    • 869提交
  • 题目提供者 朝田诗乃
  • 评测方式 云端评测
  • 标签 二分图 匈牙利算法 枚举,暴力
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    众周所知,在西洋棋中,我们有城堡、骑士、皇后、主教和长脖子鹿。

    题目描述

    如图所示,西洋棋的“长脖子鹿”,类似于中国象棋的马,但按照“目”字攻击,且没有中国象棋“别马腿”的规则。(因为长脖子鹿没有马腿)

    avatar

    给定一个$N * M$,的棋盘,有一些格子禁止放棋子。问棋盘上最多能放多少个不能互相攻击的长脖子鹿。

    输入输出格式

    输入格式:

    输入的第一行为两个正整数$N$,$M$,$K$。其中$K$表示禁止放置长脖子鹿的格子数。

    第$2$~第$K+1$行每一行为两个整数$Xi, Yi$,表示禁止放置的格子。

    输出格式:

    一行一个正整数,表示最多能放置的长脖子鹿个数。

    输入输出样例

    输入样例#1: 复制
    2 2 1
    1 1
    输出样例#1: 复制
    3
    输入样例#2: 复制
    /*额外提供一组数据*/
    8 7 5
    1 1
    5 4
    2 3
    4 7
    8 3
    输出样例#2: 复制
    28

    说明

    重要提示:请务必思考对图的遍历顺序对运行速度的影响

    对于$10$%的数据, $1 ≤ N,M ≤ 5$

    对于$30$%的数据, $1 ≤ N,M ≤ 10$

    对于$60$%的数据, $1 ≤ N,M ≤ 50$

    对于$80$%的数据, $1 ≤ N,M ≤ 100$

    对于$100$%的数据,$1 ≤ N,M ≤ 200$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。