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

题意：有N个阴珠子和N个阳珠子，特定序号的阴阳珠子放在一起会让阳珠子暗淡。现在问排放成一个环，如何排放能让暗淡的阳珠子尽可能地少。

既要考虑阳珠子的位置也要考虑阴珠子的位置，可以先枚举阴珠子成环的全排列，由于成环所以N个珠子只需要枚举N-1个数的全排列。每一次固定阴珠子的一个排列，这时候阳珠子和阴珠子的位置确定了。下面看看有多少对阴阳珠子的结合会使相邻的阳珠子暗淡，二分图跑出暗淡的阳珠子数，用n减去最大匹配就是不暗淡的。

1 #include 
     
       2 using namespace std; 3  4 const int maxn = 15; 5 int nu, nv; 6 int G[maxn][maxn]; 7 int linker[maxn]; 8 bool vis[maxn]; 9 10 bool dfs(int u) {11     for(int v = 1; v <= nv; v++) {12         if(G[u][v] && !vis[v]) {13             vis[v] = 1;14             if(linker[v] == -1 || dfs(linker[v])) {15                 linker[v] = u;16                 return 1;17             }18         }19     }20     return 0;21 }22 23 int hungary() {24     int ret = 0;25     memset(linker, -1, sizeof(linker));26     for(int u = 1; u <= nu; u++) {27         memset(vis, 0, sizeof(vis));28         if(dfs(u)) ret++;29     }30     return ret;31 }32 33 int n, m;34 int a[maxn];35 bool sb[maxn][maxn];36 37 int main() {38     // freopen("in", "r", stdin);39     int x, y;40     while(~scanf("%d%d",&n,&m)) {41         nu = nv = n;42         memset(sb, 0, sizeof(sb));43         for(int i = 1; i <= n; i++) a[i] = i;44         a[n+1] = 1;45         for(int i = 0; i < m; i++) {46             scanf("%d %d", &x, &y);47             sb[x][y] = 1;48         }49         if(n == 0) {50             printf("0\n");51             continue;52         }53         int ret = maxn;54         do {55             memset(G, 0, sizeof(G));56             for(int i = 1; i <= n; i++) {57                 for(int j = 1; j <= n; j++) {58                     if(!sb[i][a[j]] && !sb[i][a[j+1]]) {59                         G[i][j] = 1;60                     }61                 }62             }63             ret = min(ret, n-hungary());64         }while(next_permutation(a+2, a+n+1));65         printf("%d\n", ret);66     }67     return 0;68 }