HDU 5727 Necklace 环排+二分图匹配

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

枚举下黑色球的排列总数是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 ;

}