【题目链接】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;
}