这是从山东大学巨巨那里学来的做法

枚举下黑色球的排列总数是8!,然后八个白球可选的位置与左右两个黑球存不存在关系建图就行

这是原话,具体一点,每次生成环排,只有互不影响的才连边

最后:注重一点,n个数环排是(n-1)!

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=2e5+;
int pos[],n,m,match[],ret;
bool vis[],used[],g[][],mp[][];
bool dfs(int u){
for(int v=;v<=n;++v){
if(!g[u][v]||used[v])continue;
used[v]=true;
if(match[v]==-||dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
}
void solve(){
memset(match,-,sizeof(match));
memset(g,false,sizeof(g));
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
if(mp[pos[i]][j]||mp[pos[i-]][j])
continue;
g[i][j]=true;
}
}
for(int i=;i<=n;++i){
if(mp[pos[]][i]||mp[pos[n]][i])
continue;
g[][i]=true;
}
int ans=;
for(int i=;i<=n;++i){
memset(used,false,sizeof(used));
if(dfs(i))++ans;
}
ret=min(ret,n-ans);
}
void get(int x){
if(ret==)return;
if(x==n+){solve();return;}
for(int i=;i<=n;++i){
if(vis[i])continue;
pos[x]=i;
vis[i]=true;
get(x+);
vis[i]=false;
}
}
int main(){
vis[]=true;pos[]=;
while(~scanf("%d%d",&n,&m)){
if(n==){
printf("0\n");
continue;
}
memset(mp,,sizeof(mp));
while(m--){
int u,v;
scanf("%d%d",&u,&v);
mp[v][u]=true;
}
ret=INF;
get();
printf("%d\n",ret);
}
return ;
}
05-08 15:24