HDU 5727 - Necklace

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

分析：    枚举 + 二分图匹配
    　　先把阴珠放好，然后将阳珠插入空位中。
    　　枚举阴珠摆放位置，将阳珠匹配到不影响两边阴珠的位置
    　　这样 ans = min( n - 最大匹配数 )
    
注意：
    　　n = 0 时 无法使用 next_permutation 函数！！

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAXN=;

 int n, m, ans;

 bool G[MAXN][MAXN], F[MAXN][MAXN], used[MAXN];

 int Linker[MAXN];

 int a[MAXN];

 bool dfs(int u)

 {

     for(int v = ;v <= n; v++) {

         if(G[u][v] && !used[v])  {

             used[v] = ;

             if(Linker[v]==-||dfs(Linker[v])) {

                 Linker[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int Hungary(){//匈牙利

     int res = ;

     memset(Linker, -, sizeof(Linker));

     for(int u = ; u <= n; u++){

         memset(used, , sizeof(used));

         if(dfs(u)) res++;

     }

     return res;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         memset(F,,sizeof(F));

         for(int i=;i<=m;i++)

         {

             int a,b;

             scanf("%d%d",&a,&b);

             F[a][b]=;

         }

         ans=;

         for(int i=;i<=n;i++) a[i]=i;

         if(n == ) { puts(""); continue; }//此时无法全排列！！！

         do//全排列

         {

             memset(G,,sizeof(G));

             for(int i = ;i <= n;i++)

             {

                 int l = a[i],r = (i == n ? a[] : a[i+]);

                 for(int u = ;u <= n; u++)

                     if( !F[u][l] && !F[u][r])//不影响两边

                         G[u][i]=;

             }

             ans=min(n - Hungary(), ans);

         } while (next_permutation(a + ,a + n + ));//因为是环,第一点不用动

         printf("%d\n",ans);

     }

 }