给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 = ;
int n, m;
vector <int> v[];
int g[][], a[], match[], vis[];
int dfs(int u)
{
for(int i = ; i < v[u].size(); i++) {
int tmp = v[u][i];
if(vis[tmp])
continue;
vis[tmp] = ;
if(match[tmp] == - || dfs(match[tmp])) {
match[tmp] = u;
return ;
}
}
return ;
}
int maxMatch()
{
mem1(match);
int ret = ;
for(int i = ; i <= n; i++) {
mem(vis);
ret += dfs(i);
}
return ret;
}
int solve()
{
for(int i = ; i < n; i++) {
a[i] = i+;
}
int ans = inf;
do {
a[n] = a[];
for(int i = ; i <= n; i++)
v[i].clear();
for(int i = ; i < n; i++) {
for(int j = ; j <= n; j++) {
if(!g[j][a[i]] && !g[j][a[i+]]) {
v[j].pb(i);
}
}
}
int tmp = maxMatch();
ans = min(ans, n-tmp);
} while(next_permutation(a+, a+n));
return ans;
}
int main()
{
int x, y;
while(~scanf("%d%d", &n, &m)) {
mem(g);
for(int i = ; i < m; i++) {
scanf("%d%d", &x, &y);
g[x][y] = ;
}
int ans;
if(n == )
ans = ;
else
ans = solve();
printf("%d\n", ans);
}
}