(图论算法之2分匹配) hdu 1281（棋盘游戏） - c++编程基础

TOP

(图论算法之2分匹配) hdu 1281（棋盘游戏）

2015-07-20 17:23:07 来源: 作者: 【大中小】浏览:2次

题意：给一个n*m的棋盘，在上面放上车，放的车之间不能相互攻击(在同一行或者同一列就能相互攻击)，并且只有某些点能放车。问最多能放多少车，其中有多少个格子必须放才能放最多的车。

这是一道很好的理解匈牙利算法的题目。首先我们求最多放多少车，这是一个行列匹配问题。假设我们用n个左边的点代表行，m个右边的点放在右边，如果一个格子(x,y)能放车，那么将左边的x和右边的y连接一起建一条边。这个一个很经典的模型，就不必多少了。用匈牙利算法求一次最大匹配。

后面这一问很好。首先我说说最暴力的方法。记录下最大匹配的中的匹配边，然后再原图中去掉这条边，看最大匹配是否和原来的相等。一次匈牙利的复杂度是O（n*m^2).

总共n次匈牙利，总的复杂度是O（n^2*m^2），对于这题100的数据是能AC的。但是如果数据量增加就要换个方法了。实际上，在求出最大匹配以后，假设(x->y)是最大匹配中的一条边，我们首先删掉这条边，并且使y失陪。此时为x寻找增光路，如果能找到，说明我们用另外的一个匹配代替了匹配（x->y）,所以(x->y)并非必须的。否者，（x->y）是必须的。注意：如果（x->y）是必须的，那么要 link[y]=x 是的x再次匹配y 到达最大匹配。另外：不管(x->)是不是必须的，都必须还原图。

方法一暴力：

VIEW CODE

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; const int mod=99999997; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3fffffff; bool G[110][110]; int link[110]; int n,m; bool vis[110]; bool match(int x) { for(int i=1;i<=m;i++) { if(G[x][i]&&(!vis[i])) { vis[i]=1; if(link[i]==-1||match(link[i])) { link[i]=x; return 1; } } } return 0; } int hungury() { int ans=0; memset(link,-1,sizeof link); for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); if(match(i)) ans++; } return ans; } int link__[110]; int main() { int k,ca=0; while(cin>>n>>m>>k) { memset(G,0,sizeof G); while(k--) { int x,y; scanf("%d %d",&x,&y); G[x][y]=1; } int aa=hungury(); int ans=0; for(int i=1;i<=m;i++) link__[i]=link[i]; for(int i=1;i<=m;i++) { if(link__[i]+1) { int x=link__[i]; G[x][i]=0; if(hungury()!=aa) ans++; G[x][i]=1; } } printf("Board %d have %d important blanks for %d chessmen.\n",++ca,ans,aa); } return 0; }

方法2: 一次找增广路

VIEW CODE

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; const int mod=99999997; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3fffffff; bool G[110][110]; int link[110]; int n,m; bool vis[110]; bool match(int x) { for(int i=1;i<=m;i++) { if(G[x][i]&&(!vis[i])) { vis[i]=1; if(link[i]==-1||match(link[i])) { link[i]=x; return 1; } } } return 0; } int hungury() { int ans=0; memset(link,-1,sizeof link); for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); if(match(i)) ans++; } return ans; } int main() { int k,ca=0; while(cin>>n>>m>>k) { memset(G,0,sizeof G); while(k--) { int x,y; scanf("%d %d",&x,&y); G[x][y]=1; } int aa=hungury(); int ans=0; for(int i=1;i<=m;i++) { if(link[i]+1) { int x=link[i]; G[x][i]=0; link[i]=-1; memset(vis,0,sizeof vis); if(!match(x)) { ans++; link[i]=x; } G[x][i]=1; } } printf("Board %d have %d important blanks for %d chessmen.\n",++ca,ans,aa); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：PAT Advanced 1005	下一篇：POJ 2175 Evacuation Plan 费用流..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: