HDU5727 Necklace

http://acm.hdu.edu.cn/showproblem.php?pid=5727

题意：n个珠子，每个珠子有阴阳两种属性，且阴的一定和阳的紧邻，排成一个环；m行，每行两个数，表示阳性x珠子和y阴性珠子相邻则功能减弱，问功能减弱珠子最少有几个

思路：二分匹配

全排列阴性珠子，因为是环，O((n-1)!)；枚举每个阳性珠子，插入i位置，前提是i前后两个阴性珠子都不与阳性珠子有排斥作用；

最后问题变转化成，阳性珠子和位置的最大匹配问题

 // #pragma comment(linker, "/STACK:102c000000,102c000000")

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 // #include <conio.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 const int N = ;

 const int M = 1e6+;

 const int MOD = 1e9+;

 #define LL long long

 #define LB long double

 #define mi() (l+r)>>1

 double const pi = acos(-);

 const double eps = 1e-;

 void fre() {

     freopen("in.txt","r",stdin);

 }

 // inline int r() {

 //     int x=0,f=1;char ch=getchar();

 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}

 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;

 // }

 int mp[][];

 int a[];

 int n,m;

 int ans;

 bool vis[];

 int b[];

 vector<int>s[];

 bool dfs(int x){

     if(vis[x]) return false;

     vis[x]=;

     for(int i=;i<(int)s[x].size();i++){

         int v=s[x][i];

         if(b[v]==-||dfs(b[v])){

             b[v]=x;

             return true;

         }

     }

     return false;

 }

 void hungarian(){

     clc(b,-);

     int tem=;

     for(int i=;i<=n;i++){

         clc(vis,);

         if(dfs(i))

             tem++;

     }

     if(tem>ans) ans=tem;

 }

 void work(){

     for(int i=;i<n;i++){

        a[i]=i+;

     }

     do{

         for(int i=;i<=;i++) s[i].clear();

         for(int i=;i<n;i++){

            int k1=a[i],k2=a[(i-+n)%n];

            for(int j=;j<=n;j++){

               if(!mp[k1][j]&&!mp[k2][j]) s[j].push_back(i);

            }

         }

         hungarian();

     }while(next_permutation(a+,a+n)&&ans!=n);

 }

 int main(){

     // fre();

     while(~scanf("%d%d",&n,&m)){

         clc(mp,);

         ans=;

         for(int i=;i<m;i++){

             int x,y;

             scanf("%d%d",&x,&y);

             mp[y][x]=;

         }

         work();

         printf("%d\n",n-ans);

     }

     return ;

 }