hdu_5727_Necklace(二分匹配)

题目连接：hdu_5727_Necklace

题意：

有2*n个珠子，n个阳珠子，n个阴珠子，现在要将这2n个珠子做成一个项链，珠子只能阴阳交替排，有些阳珠子周围如果放了指定的阴珠子就会变坏，给你一个n和m个关系x y，这些关系指明了阳珠子x周围放y阴珠子会变坏，现在问你做成这条项链，最少变坏的阳珠子有多少个

题解：

官方题解给的是用DFS 带剪枝来做，不过我感觉那样好玄学，我的做法是将所有的阴珠子可能组成的组合全部算出来，然后用阳珠子去插空，这里插空我们要找最大的匹配，也就是我们可以用二分匹配来做，为什么要找最大匹配，因为我们要得到最少的变坏珠子，我们要找到阳珠子在不变坏的情况下最多可以放的个数。然后就是建图，

我们先把二分图的所有的边都连上，然后如果发现阳珠子在这个空会变坏，那么我们就删除这条边，最后跑匈牙利跑出来就是最大的不会变坏的阳珠子个数，然后我们维护一下每种阴珠子的排列方式下的ans，总时间复杂度为（n-1）！*n²这里n<=9，所以随便能跑过，为什么是n-1,因为这是一个环，我们可以固定其中一个点，这样可以少一个阶，当然你还可以优化到（（n-1）！*n²）/2，因为这个环你从左边开始排和从右边开始排石一样的。

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=111;
int g[N],nxt[N],v[N],ed,n,m,x,y,f[11],b[11],G[11][11];

inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
inline void up(int &a,int b){if(a>b)a=b;}

int find(int x,int m)
{
    F(i,1,m)
        if(G[x][i]&&!b[i])
        {
            b[i]=1;
            if(!f[i]||find(f[i],m))return f[i]=x,1;
        }
    return 0;
}

int hungry(int n,int m,int ans=0)
{
    mst(f,0);
    F(i,1,n)mst(b,0),ans+=find(i,m);
    return ans;
}

int main(){
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0||m==0){puts("0");continue;}
        mst(g,0),ed=0;
        F(i,1,m)scanf("%d%d",&x,&y),adg(y,x);
        int now[11],ans=1000;
        F(i,1,n)now[i]=i;
        do{
            F(i,1,n)F(j,1,n)G[i][j]=1;
            F(ic,1,n)for(int i=g[now[ic]];i;i=nxt[i])
            if(ic==1)G[1][v[i]]=G[n][v[i]]=0;
                else G[ic][v[i]]=G[ic-1][v[i]]=0;
            up(ans,n-hungry(n,n));
            if(!ans)break;
        }while(next_permutation(now+2,now+1+n));
        printf("%d
",ans);
    }
    return 0;
}