HDU-5727

Problem Description:

SJX has 2*N magic gems. N of them have Yin energy inside while others have Yang energy. 
SJX wants to make a necklace with these magic gems for his beloved BHB. 
To avoid making the necklace too Yin or too Yang, he must place these magic gems Yin after Yang and Yang after Yin, which means two adjacent gems must have different kind of energy. 
But he finds that some gems with Yang energy will become somber adjacent with some of the Yin gems and impact the value of the neckless. 
After trying multiple times, he finds out M rules of the gems. He wants to have a most valuable neckless which means the somber gems must be as less as possible. 
So he wonders how many gems with Yang energy will become somber if he make the necklace in the best way.

Input:

  Multiple test cases.

  For each test case, the first line contains two integers N(0≤N≤9),M(0≤M≤N∗N), descripted as above.

  Then M lines followed, every line contains two integers X,Y, indicates that magic gem X with Yang energy will become somber adjacent with the magic gem Y with Yin energy.

Output:

One line per case, an integer indicates that how many gem will become somber at least.

 

　　当看到 “0≤N≤9” 时，第一感觉一定是暴力，枚举一种珠子的组合仅仅需要 8! ，这还不暴力，但思路到这好像就断了......

　　再看这道题，感觉又好像是二分图的最大匹配，但怎么连边，that`s is a question.

　　放翁有言：山重水复疑无路，柳暗花明又一村。我们把上面两个思路连起来，似乎就有想法了：

　　枚举阴间珠子的组合，由于阴阳相隔，所以每个阴间珠子之间的空隙(下图红色位置)一定放的是阳间珠子，讨论每个空格能放哪些珠子，用二分图解决就好了。

　　最后说一下，排列用 next_permutation 解决，具体用可以百度一下。

　　Code：

 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
bool Map[15][15];
int n,m,x,y,On[25],Pos[25],ans,Mark[25],Cnt,Head[25],Next[205],To[205],Ans;
inline int read()
{
    int x(0);char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
inline void ADD(int x,int y) {Next[++Cnt]=Head[x],Head[x]=Cnt,To[Cnt]=y;}
inline bool DFS(int x)
{
    for(register int i=Head[x];i;i=Next[i])
    {
        int j=To[i];
        if(Mark[j]!=Cnt)
        {
            Mark[j]=Cnt;
            if(!On[j]||DFS(On[j])) {On[j]=x;return 1;}
        }    
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        m=read(),Ans=10,memset(Map,0,sizeof Map);
        for(register int i=1;i<=m;++i) x=read(),y=read(),Map[x][y]=1;
        if(!n||!m) {printf("0\n");continue;}
        for(register int i=1;i<=n;++i) Pos[i]=i;
        do
        {
            ans=Cnt=0,memset(Head,0,sizeof Head),memset(On,0,sizeof On),memset(Mark,0,sizeof Mark);
            for(register int i=1;i<=n;++i)
                for(register int j=1;j<=n;++j)
                {
                    if(i==1) x=Pos[n],y=Pos[1];
                    else x=Pos[i-1],y=Pos[i];
                    if(!Map[j][x]&&!Map[j][y]) ADD(j,i);
                }
            Cnt=0;
            for(register int i=1;i<=n;++i) ++Cnt,ans+=DFS(i);
            Ans=min(Ans,n-ans);
        }while(next_permutation(Pos+2,Pos+n+1));
        printf("%d\n",Ans);
    }
    return 0;
}

View Code