hdu5727 Necklace（二分图）

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=120+5;
#define INF 999999
int ans = 0;
int vis[maxn],pos[maxn];
int n,m;
int mp[20][20];
struct Max_Match
{
    int n;
    vector<int> g[maxn];
//	int g[maxn][maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=1; i<=n; ++i) g[i].clear();
	   // memset(g,0,sizeof(g));
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int i=0;i<g[u].size();++i)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1; i<=n; ++i)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ++ans;
        }
        return ans;
    }
}MM;
void work()
{
     MM.init(n*2);
	 for(int i = 2;i<=n;i++)
		 for(int j = 1;j<=n;j++)
		 {
			  if(mp[pos[i]][j] || mp[pos[i-1]][j])
				  continue;
			  MM.g[i].push_back(j);
		 }
	 for(int i = 1;i<=n;i++)
	 {  
		 if(mp[pos[1]][i] || mp[pos[n]][i])
			 continue;
         MM.g[1].push_back(i);
	 }
	 ans = min(ans,n-MM.solve());
}
int jianzhi = 0;
void shengchengquanpailie(int cnt)
{
//	 jianzhi++;
//	 if(jianzhi>100000)
//		 return;
	 if(!ans)
		 return;
     if(cnt==n+1)
	 {
		 work();
		 return;
	 }
     for(int i = 1;i<=n;i++)
	 {
		 if(vis[i])
			 continue;
		 pos[cnt]=i;
		 vis[i]=1; 
		 shengchengquanpailie(cnt+1);
		 pos[cnt]=0;
		 vis[i]=0;
	 }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
		if(n==0)
		{
			printf("0\n");
			continue;
		}
		memset(vis,0,sizeof(vis));
		memset(pos,0,sizeof(pos));
		memset(mp,0,sizeof(mp));
		jianzhi = 0;
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
			mp[v][u]=1;
        }
        ans = INF;
		pos[1]=1;
		vis[1]=1;
		shengchengquanpailie(2);
		printf("%d\n",ans);
    }
    return 0;
}