博客

题目链接：

点这里！！！

题意：

有2n(0<=n<=9)个珠子，分成阴阳两极，每极各n个


。

用这2n个珠子做成一个项链，使得相邻两个珠子的极性是不一样的，因为有一些阳性的珠子会被一些阴性的珠子所削弱在它们它们相邻的情况下。

给你m(0<=m<=n*(n-1)/2)个关系[x,y]表示阳性珠子x会被阴性珠子y在相邻情况下所削弱。问你最少有多少个阳性被削弱。

题解：

我们可以先暴力枚举出所有阴性珠子的排列情况(因为是环，所以有(n-1)!种)，然后在它们之间插入阳性的珠子，判断出阳性珠子插入在之间会不会被削弱。我们通过匈牙利算法算出最大匹配sum，然后算出n-sum,对于每种排列取最小值就得到了我们想要的答案，注意特判下n=0的情况。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#include<cmath>
#define LL long long
#define pb push_back
#define pa pair<int,int>
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define bug(x) printf("%d++++++++++++++++++++%d\n",x,x)
#define key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:102400000000,102400000000")
const LL  MOD = 1000000007;
const int N = 20;
const int maxn = 1e5+15;
const int letter = 130;
const LL INF = 1e18;
const double pi=acos(-1.0);
const double eps=1e-10;
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int mp[N][N],vis[N],mark[N],pos[N],f[N][N];
bool dfs(int x){
    for(int i=1;i<=2*n;i++){
        if(f[x][i]&&!vis[i]){
            vis[i]=1;
            if(mark[i]==-1||dfs(mark[i])){
                mark[i]=x;
                return true;
            }
        }
    }
    return false;
}
void solve(){
    for(int i=1;i<=n;i++) pos[i]=i;
    int ans=n;
    do{
        clr(mark,-1);
        clr(f,0);
        int x,y;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==1) x=pos[i],y=pos[n];
                else x=pos[i],y=pos[i-1];
                if(mp[x][j]||mp[y][j]) continue;
                f[i][j]=1;
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            clr(vis,0);
            if(dfs(i)) sum++;
        }
        ans=min(ans,n-sum);
    }while(next_permutation(pos+2,pos+n+1));
    printf("%d\n",ans);
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        if(n==0){
            puts("0");
            continue;
        }
        clr(mp,0);
        int x,y;
        for(int i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            mp[y][x]=1;
        }
        solve();
    }
    return 0;
}