HDU-1281-棋盘游戏(最大匹配，枚举)-白红宇

HDU-1281-棋盘游戏(最大匹配，枚举)

阅读量：7239 次

发布时间：2019-06-29

本文共 1630 字，大约阅读时间需要 5 分钟。

链接：

题目：

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

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

思路：

根据x和y建立二分图，求最大匹配，再通过枚举x，y点，挨个消除点进行最大匹配，当某个点被消除以后，最大匹配减小，则这个点为关键点。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long LL;const int MAXN = 2000+10;vector
                    
                      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;}

转载于:https://www.cnblogs.com/YDDDD/p/10870019.html

你可能感兴趣的文章

Struts2遇到Caused by Action class not found这类问题怎么解决