HDU-1281-棋盘游戏(最大匹配,枚举)
2024-09-29 20:23:04
链接:https://vjudge.net/problem/HDU-1281
题目:
小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解决这个问题么?
思路:
根据x和y建立二分图,求最大匹配,再通过枚举x,y点,挨个消除点进行最大匹配,当某个点被消除以后,最大匹配减小,则这个点为关键点。
代码:
#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <cstdio>
#include <set>
#include <iterator>
#include <cstring>
using namespace std; typedef long long LL;
const int MAXN = 2000+10;
vector<int> G[MAXN];
int Map[200][200];
int Link[MAXN], Vis[MAXN];
int n, m, k; void Init()
{
for (int i = 1;i <= n;i++)
G[i].clear();
} bool Dfs(int x)
{
for (int i = 1;i <= m;i++)
{
if (Map[x][i] && Vis[i] == 0)
{
Vis[i] = 1;
if (Link[i] == -1 || Dfs(Link[i]))
{
Link[i] = x;
return true;
}
}
}
return false;
} int Solve()
{
memset(Link, -1, sizeof(Link));
int cnt = 0;
for (int i = 1;i <= n;i++)
{
memset(Vis, 0, sizeof(Vis));
if (Dfs(i))
cnt++;
}
return cnt;
} int main()
{
int pos = 0;
while (~scanf("%d%d%d", &n, &m, &k))
{
memset(Map, 0, sizeof(Map));
int x, y;
for (int i = 1;i <= k;i++)
{
scanf("%d%d", &x, &y);
Map[x][y] = 1;
}
int cnt = Solve(), res = 0;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
if (Map[i][j])
{
Map[i][j] = 0;
int tmp = Solve();
Map[i][j] = 1;
if (tmp < cnt)
res++;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", ++pos, res, cnt);
} return 0;
}
最新文章
- yum安装mysql和mysql源,配置mysql
- win10没有新建文件夹
- react路由案例(非常适合入门)
- HDU 4757 Tree
- IDL中histogram的应用
- 检测是否安装有sim卡
- Php的安装与配置
- partial局部类
- frontpage 正则 查找与替换
- 安装fedora 16 之后
- Clamp函数
- 信息存储——当值X是2的非负整数n次幂时,如何表示成十六进制
- hdu_1536_S-Nim(DFS_SG博弈)
- Angular02 将数据添加到组件中
- Linux_服务器_01_查看公网IP
- Flume介绍
- VIM编辑器操作命令积累
- 《java入门第一季》之面向对象(内部类到底在哪里?)
- LODOP打印用JS获取的当前日期
- Floyd算法_MATLAB