hdu 5727 Necklace 二分图匹配

题目链接

给2*n个珠子， n<=9， n个阴n个阳。 然后将它们弄成一个环， 阴阳交替。现在给你m个关系， 每个关系给出a， b。 如果阳a和阴b挨着， 那么a就会变暗。 问你最小变暗几个阳。

我们求出阴的所有全排列， 是9！， 因为形成一个环。 所以可以想象成一个珠子是固定不变的， 剩下n-1个变， 所以就是8！。 然后对于每种情况， 就是我们熟悉的二分图匹配了。 对于两个阴珠之间的空隙， 如果阳珠可以放到这里就连一条边。 然后跑匈牙利匹配就可以了。 9！过不了...

#include <bits/stdc++.h>

using namespace std;
#define pb(x) push_back(x)
#define mem(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
const int inf = 1061109567;
int n, m;
vector <int> v[11];
int g[11][11], a[11], match[11], vis[11];
int dfs(int u)
{
    for(int i = 0; i < v[u].size(); i++) {
        int tmp = v[u][i];
        if(vis[tmp])
            continue;
        vis[tmp] = 1;
        if(match[tmp] == -1 || dfs(match[tmp])) {
            match[tmp] = u;
            return 1;
        }
    }
    return 0;
}
int maxMatch()
{
    mem1(match);
    int ret = 0;
    for(int i = 1; i <= n; i++) {
        mem(vis);
        ret += dfs(i);
    }
    return ret;
}
int solve()
{
    for(int i = 0; i < n; i++) {
        a[i] = i+1;
    }
    int ans = inf;
    do {
        a[n] = a[0];
        for(int i = 1; i <= n; i++)
            v[i].clear();
        for(int i = 0; i < n; i++) {
            for(int j = 1; j <= n; j++) {
                if(!g[j][a[i]] && !g[j][a[i+1]]) {
                    v[j].pb(i);
                }
            }
        }
        int tmp = maxMatch();
        ans = min(ans, n-tmp);
    } while(next_permutation(a+1, a+n));
    return ans;
}
int main()
{
    int x, y;
    while(~scanf("%d%d", &n, &m)) {
        mem(g);
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &x, &y);
            g[x][y] = 1;
        }
        int ans;
        if(n == 0)
            ans = 0;
        else
            ans = solve();
        printf("%d
", ans);
    }
}