HDU 5727 Necklace(二分图匹配)
【题目链接】 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; }