题目大概说有n个yang珠子n个yin珠子，要交替串成一个环形项链，有些yang珠子和某个yin珠子相邻这个yang珠子会不高兴，问最少有几个yang珠子不高兴。
自然会想到直接用状压DP去解，转移很烦，也没写出来。标程是搜索不明觉厉。。听闻了可以枚举一边的顺序，8!，然后用最大匹配解决。
然后想到的是枚举yang的顺序，然后对于每一个yang去其匹配下一个的yin，即X部是yang，而Y部是yin。不过这样开头那个yang可能出现少算的情况。。这个搞了好久都不行。。
其实，枚举yin的顺序，X部是各个yang，而Y部是位置！然后问题就引刃而解。我太菜了。。
另外用最大流超时了，然后用了个匈牙利过了，O((n-1)!*n)的时间复杂度。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,map[][],mat[];
bool used[];
bool crosspath(int k){
for(int i=; i<=map[k][]; ++i){
int j=map[k][i];
if(!used[j]){
used[j]=true;
if(mat[j]== || crosspath(mat[j])){
mat[j]=k;
return true;
}
}
}
return false;
} int hungary(){
int res=;
for(int i=; i<=n; ++i){
memset(used,,sizeof(used));
if(crosspath(i)) ++res;
}
return res;
} bool rel[][];
int main(){
int m;
while(~scanf("%d%d",&n,&m)){
memset(rel,,sizeof(rel));
int a,b;
while(m--){
scanf("%d%d",&a,&b);
rel[a][b]=;
} if(n== && rel[][]){
puts("");
continue;
}
if(n<=){
puts("");
continue;
} int seq[];
for(int i=; i<=n; ++i){
seq[i]=i;
} int res=;
do{
for(int i=; i<=*n; ++i) map[i][]=;
memset(mat,,sizeof(mat));
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
if(rel[i][seq[j]] || rel[i][seq[j%n+]]) continue;
map[i][++map[i][]]=j+n;
map[j+n][++map[j+n][]]=i;
}
}
res=max(res,hungary());
}while(next_permutation(seq+,seq++n));
printf("%d\n",n-res);
}
return ;
}