hdu 1281 棋盘游戏（最大匹配·匈牙利）

hdu 1281 棋盘游戏（最大匹配·匈牙利）

题目：​​class="data-table" data-id="t7a7e9d1-8Bm8T5OB" data-width="" style="outline: none; border-collapse: collapse; width: 100%;">

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

​​Submit​​​​Status​​

Description

小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。

所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？

Input

输入包含多组数据， 第一行有三个数N、M、K(1

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.

Source

杭电ACM集训队训练赛（VI）

分析：车可以吃掉所在的行所在的列所有棋子，所以所在行和列构成了一个匹配，选中一个棋子，它所在行和所在列的可选点就不能放棋子了。这和二分匹配联系在一起，最大的匹配数就是最多放多少个车。至于那些重要点，可以逐一测试，如果没有这一点，匹配数会不会减小，减小了就是重要点。

#include #include #include using namespace std;const int maxn=1e2+10;int n,m,k;bool bmap[maxn][maxn],bmask[maxn];int nx,ny;int cx[maxn],cy[maxn];int findpath(int u){ for(int j=1;j<=ny;j++){ if(bmap[u][j] && !bmask[j]){ bmask[j]=1; if(cy[j]==-1 || findpath(cy[j])){ cy[j]=u; cx[u]=j; return 1; } } } return 0;}int maxmatch(){ int res=0; memset(cx,-1,sizeof(cx)); memset(cy,-1,sizeof(cy)); for(int i=1;i<=nx;i++){ if(cx[i]==-1){ for(int j=1;j<=ny;j++) bmask[j]=0; res+=findpath(i); } } return res;}int main(){ //freopen("cin.txt","r",stdin); int ca=1; while(cin>>n>>m>>k){ int a,b; memset(bmap,0,sizeof(bmap)); for(int i=1;i<=k;i++){ scanf("%d%d",&a,&b); bmap[a][b]=1; } nx=n; ny=m; int q2=maxmatch(),q1=0; for(int i=1;i<=nx;i++){ for(int j=1;j<=ny;j++){ if(bmap[i][j]) { bmap[i][j]=0; int temp=maxmatch(); if(temp

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。