/*
题解:枚举 + 二分图最大匹配
棋盘行和列分别作AB集合,如果可以放旗子,则Ai 与 Bi连一条边,令map[i][j] = 1。同行与同列至多存在一个棋子,等于同一个点只能被一条边覆盖,于是棋盘中可以放最多棋子问题便转换成寻找最大匹配问题。由于本题中要求找出存在多少关键点,枚举每一个map[i][j] = 1的点,如果将map[i][j] = 0后,得到最大匹配值小于原来最大匹配值,则该节点为关键点。
*/
#include <iostream>
using namespace std;
const int nMax = 105;
int link[nMax];
int useif[nMax];
int map[nMax][nMax];
int n, m, k;
int getPath(int t)
{
for(int i = 0; i < m; ++ i)
{
if(!useif[i] && map[t][i])
{
useif[i] = 1;
if(link[i] == -1 || getPath(link[i]))
{
link[i] = t;
return 1;
}
}
}
return 0;
}
int getNum()
{
int ans = 0;
memset(link, -1, sizeof(link));
for(int i = 0; i < n; ++ i)
{
memset(useif, 0, sizeof(useif));
ans += getPath(i);
}
return ans;
}
int main()
{
//freopen("f://data.in", "r", stdin);
int cas = 0;
while(scanf("%d %d %d", &n, &m, &k) != EOF)
{
memset(map, 0, sizeof(map));
while(k --)
{
int a, b;
scanf("%d %d", &a, &b);
-- a;
-- b;
map[a][b] = 1;
}
int num = getNum();
int ans = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
if(map[i][j])
{
map[i][j] = 0;
if(getNum() < num)
ans ++;
map[i][j] = 1;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", ++cas, ans, num);
}
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
acm hdu as easy as a+b
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 1695 GCD(欧拉函数+容斥原理).docx
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
HDUACM2010版13二分匹配及其应用.ppt
hdu1001解题报告