HDUOJ 5727 Necklace

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5727

题意:给定n个阳珠子,n个阴珠子。部分阳珠子和阴珠子有排斥关系,阳珠子若和这些阴珠子放在一起会变暗,问怎样环形排列阳珠子,可以使得阳珠子变暗的次数最少。

思路:由于n很小所以我们可以先用全排列出阴珠子的位置,然后放阳珠子,如果阳珠子放入时不会变暗就连一条边,然后跑一下匈牙利求最大匹配,n-最大匹配就是当前位置阳珠子最少的变暗次数。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=10;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-10;
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m;
int yin[maxn],pre[maxn];
bool rel[maxn][maxn],vis[maxn][maxn],used[maxn];
void init(){
    clr(rel,false);
}
bool dfs(int x){
    for (int i=1;i<=n;i++){
        if (vis[x][i] && !used[i]){
            used[i]=true;
            if (pre[i]==0 || dfs(pre[i])){
                pre[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    while (~scanf("%d%d",&n,&m)){
        if (n==0){
            for (int i=0;i<m;i++){
                int a,b;
                read(a),read(b);
            }
            puts("0");
            continue;
        }
        init();
        for (int i=0;i<m;i++){
            int a,b;read(a),read(b);
            rel[a][b]=true;
        }
        for (int i=1;i<=n;i++) yin[i]=i;
        int ans=INF;
        do{
            clr(vis,false);
            for (int i=1;i<n;i++){
                for (int j=1;j<=n;j++){
                    if ((!rel[j][yin[i]])&&(!rel[j][yin[i+1]]))
                        vis[i][j]=true;
                }
            }
            for (int i=1;i<=n;i++){
                if ((!rel[i][yin[n]])&&(!rel[i][yin[1]]))
                    vis[n][i]=true;
            }
            int cnt=0;
            clr(pre,0);
            for (int i=1;i<=n;i++){
                clr(used,false);
                if (dfs(i)) cnt++;
            }
            ans=min(ans,n-cnt);
        }while (next_permutation(yin+2,yin+1+n) && ans);//从yin+2开始是因为项链是环状的,yin+1开始的排列就会有重复
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注