HDU 5727 Necklace(二分图匹配)

forever97 posted @ 2016年7月22日 00:27 in 图论-二分图匹配 with tags 二分图匹配 匈牙利算法 , 393 阅读

 

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5727

 

【题目大意】

    现在有n颗阴珠子和n颗阳珠子,将它们阴阳相间圆排列构成一个环,已知有些阴珠子和阳珠子不能放在相邻的位置,否则这颗阳珠子就会失去功效,输出最少失去能量的阳珠子数目

 

【题解】

    对于阴珠子固定的排列方式,可以用算出阳珠子能够不失去能量就能够放置的位置,将这种关系看成一条边,进行二分图匹配,就可以得不失去能量的阳珠子的最大值,显然就可以获得最少失去能量的数目。

    注意在此题中,不知道阴珠子的排列方式,因此,我们需要枚举阴珠子的不同排列方式,由于阴珠子是一个圆排列,因此只要枚举(排列长度-1)的排列即可(注:笔者枚举全排列后超时)。在不同排列的最大匹配中取最大值,用n减去这个值就可以得到答案了。

 

【代码】

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int N=20;
int n,m,ans,x,y,Link[N],g[N][N],used[N],a[N],p[N],f[N][N];
int Dfs(int x){
    rep(i,n){
        if(g[x][i]&&!used[i]){
            used[i]=1;
            if(Link[i]==-1||Dfs(Link[i])){Link[i]=x;return 1;}
        }
    }return 0;
}
int Hungarian(){
    int count=0;
    memset(Link,-1,sizeof(Link));
    rep(i,n){
        memset(used,0,sizeof(used));
        if(Dfs(i))count++;
    }return count;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(f,0,sizeof(f));ans=INT_MAX;
        for(int i=0;i<m;i++)scanf("%d%d",&x,&y),f[x][y]=1;
        if(n==0){puts("0");continue;}
        if(n==1){puts(f[1][1]?"1":"0");continue;}
        for(int i=0;i<n;i++)p[i]=i+1;
        do{
            memset(g,0,sizeof(g));
            rep(i,n)rep(j,n)if(!f[i+1][p[j]]&&!f[i+1][p[(j+1)%n]])g[i][j]=1;
            ans=min(ans,n-Hungarian());
        }while(next_permutation(p+1,p+n));
        printf("%d\n",ans);
    }return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter