`

hdu 1281 棋盘游戏(二分图求关键点)

阅读更多



 棋盘游戏

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 852    Accepted Submission(s): 492

Problem Description
小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解决这个问题么? 

 

Input

 

输入包含多组数据,
第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M),表示了棋盘的高、宽,以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息:每行两个数X和Y,表示了这个格子在棋盘中的位置。

 

Output
对输入的每组数据,按照如下格式输出:
Board T have C important blanks for L chessmen.
Sample Input
3 3 4 1 2 1 3 2 1 2 2 3 3 4 1 2 1 3 2 1 3 2

 

Sample Output
Board 1 have 0 important blanks for 2 chessmen. Board 2 have 3 important blanks for 3 chessmen.
             这题主要难点是寻找关键点。不过其实也不算难,先求出最大匹配sum,然后分别将每一个点(x,y)分别去掉,与sum比较,如果比sum小则证明这个点是关键点,以此类推。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

const int N = 105;

bool map[N][N], flag[N];
int pre[N], c[N*N][2];
int n, m, k;

int find(int cur)   //匈牙利算法(二分匹配)
{
    int i;
    for(i = 1; i <= m; i++)
    {
        if(map[cur][i] && !flag[i])
        {
            flag[i] = true;
            if(pre[i] == -1 || find(pre[i]))
            {
                pre[i] = cur;
                return 1;
            }
        }
    }
    return 0;
}

int run()
{
    int i, sum = 0;
    memset(pre, -1, sizeof(pre));
    for(i = 1; i <= n; i++)
    {
        memset(flag, false, sizeof(flag));
        sum += find(i);
    }
    return sum;
}

int main()
{
    int i, x, y, sum, ans, num, zz = 1;
    while(scanf("%d %d %d", &n, &m, &k) != EOF)
    {
        memset(map, false, sizeof(map));
        memset(c, 0, sizeof(c));
        for(i = 1; i <= k; i++)
        {
            scanf("%d %d", &x, &y);
            map[x][y] = true;       //建图
            c[i][0] = x;    //行
            c[i][1] = y;    //列
        }
        sum = run();
        ans = 0;
        for(i = 1; i <= k; i++)     //分别枚举每条边(x,y)
        {
            map[ c[i][0] ][ c[i][1] ] = false;
            num = run();
            if(num < sum) ans++;    //比sum少,证明那条边关键点(x,y)
            map[ c[i][0] ][ c[i][1] ] = true;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n", zz++, ans, sum);
    }

    return 0;
}
 
  • 大小: 2.7 KB
1
6
分享到:
评论

相关推荐

    二分图的完美匹配 KM算法.docx

    二分图的完美匹配是指在一个图中,每个顶点恰好被一条边连接,使得图中的所有顶点都被连接且没有多余未使用的边。在实际应用中,二分图的完美匹配常常出现在分配问题、调度问题等领域。KM算法,即Kuhn-Munkres算法,...

    二分匹配题集

    5. **棋盘游戏 (HDU 1281)** - **知识点**:行列匹配问题。 - **解题思路**:构建行列二分图,对于每个行顶点连接该行上的所有列顶点,然后使用最大匹配算法求解。 6. **50 years, 50 colors (HDU 1498)** - *...

    hdu.rar_hdu

    通过研究这些代码,你可以学到以下关键知识点: 1. **基础算法**:如排序(冒泡、选择、插入、快速、归并等)、搜索(线性、二分、深度优先、广度优先等)。 2. **高级算法**:包括动态规划(状态转移、记忆化搜索...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    ACM HDU题目分类

    搜索题是 ACM HDU 题目分类中的一大类,例如,1010 搜索题,剪枝很关键;1016 经典的搜索;1026 搜索;1043 经典搜索题,八数码问题;1044 稍微有点麻烦的搜索题;1045 搜索题,可用匹配做 等等。 贪心算法 贪心...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    我的ACM个人模板模板

    根据给定的信息,我们可以总结出以下关于二分图检测的相关知识点: ### 一、二分图定义 二分图(Bipartite Graph)是一种特殊的图,在数学领域中,一个图G=(V,E)被称为二分图,如果其顶点集V能被划分成两个互不...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu1001解题报告

    hdu1001解题报告

    hdu acm 教案(7)

    在这个章节中,你可能会学到以下几个关键知识点: 1. **深度优先搜索(DFS, Depth-First Search)**:DFS是一种遍历或搜索树(或图)的算法,它沿着树的深度方向进行探索,直到达到叶子节点或者回溯到一个未被访问...

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU ACM 培训资料

    HDU ACM培训资料是一系列专为参与ACM(国际大学生程序设计竞赛)的学员准备的教育资源,涵盖了算法和编程竞赛的核心知识。这份压缩包包含了11个不同主题的课时,旨在帮助学员全面掌握ACM竞赛所需的技能。下面将详细...

    ACM HDU

    ACM HDU题目的解决方案通常会涉及以下知识点: 1. **基础算法**:包括排序(快速排序、归并排序等)、搜索(二分查找、深度优先搜索等)、图论(最短路径、最小生成树等)。 2. **动态规划**:解决许多具有重叠子...

    HDU图论题目分类

    以下是HDU图论题目分类中的部分知识点: 1. 图的基本概念:图的定义、图的表示、图的遍历、图的搜索等。 * 题目1010:Tempter of the Bone,涉及到递归搜索的概念。 * 题目1016:Prime Ring Problem,涉及到递归...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

Global site tag (gtag.js) - Google Analytics