HDU 5727 Necklace ( 2016多校、二分图匹配 )

时间：2021-09-15 23:51:43

题目链接

题意 : 给出 2*N 颗珠子、有 N 颗是阴的、有 N 颗是阳的、现在要把阴阳珠子串成一个环状的项链、而且要求珠子的放置方式必须的阴阳相间的、然后给出你 M 个限制关系、格式为 ( A、B ) 表示如果阳性 A 珠子和阴性 B 珠子相邻的话、那么阳性珠子就会衰弱、问你在最优的情况下、最少有多少颗阳珠子是衰弱的

分析 :

看题目 N 的大小只有 9

不免让人浮想联翩、跃跃欲试枚举暴力

直接暴力还是不行的

首先先枚举阴珠子所在的位置

这个可以用 next_permutation 解决

然后对于阴珠子之间的位置、到底填哪些阳珠子进去呢？

其实可以使用二分图匹配的方式

将每个位置与放到这个位置不衰弱的阳珠子相连

最后进行二分图最大匹配、答案就是 Min( N - Match() )

即最小的 N - 最大匹配结果

在 next_permutation 的时候、由于是环状的

所以不必 next_permutation 所有的阴珠子

保持其中一个不变也可以解决此题

则枚举全排列复杂度就从 9! 优化到了 8!

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long

#define scl(i) scanf("%lld", &i)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l)

#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)
#define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l)
#define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l)
#define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l)

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))

#define fir first
#define sec second
#define VI vector<int>
#define ins(i) insert(i)
#define pb(i) push_back(i)
#define pii pair<int, int>
#define VL vector<long long>
#define mk(i, j) make_pair(i, j)
#define all(i) i.begin(), i.end()
#define pll pair<long long, long long>

#define _TIME 0
#define _INPUT 0
#define _OUTPUT 0
clock_t START, END;
void __stTIME();
void __enTIME();
void __IOPUT();
using namespace std;
;
int N, M;
int arr[maxn], match[maxn];
int G[maxn][maxn];
bool used[maxn];
bool mp[maxn][maxn];

];
int Head[maxn], cnt;

inline void init()
{
    mem(Head, -);
    cnt = ;
}

inline void AddEdge(int from, int to)
{
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

bool DFS(int v)
{
    used[v] = true;
    ; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        int w = match[Eiv];
         || !used[w] && DFS(w)){
            match[v] = Eiv;
            match[Eiv] = v;
            return true;
        }
    }
    return false;
}

int GetMatch()
{
    ;
    memset(match, -, sizeof(match));
    ; i<=(N<<); i++)
        ){
            memset(used, false, sizeof(used));
            if(DFS(i))
                ret++;
        }
    return ret;
}

int main(void){__stTIME();__IOPUT();

    while(~scii(N, M)){

         || M == ){
            puts(");
            continue;
        }

        mem(mp, false);

        ; i<M; i++){
            int A, B;
            scii(A, B);
            mp[A][B] = true;
        }
        ; i<=N-; i++) arr[i] = i; arr[N] = N;

        <<);

        do{

            //for(int i=1; i<=N; i++) printf("%d ", arr[i]); puts("");

            init();

            ; k<=N; k++){
                int i = k + N;
                int L = arr[k];
                ]) : (arr[k+]);
                ; j<=N; j++){
                    if(mp[j][L] || mp[j][R]) continue;
                    else{
//                        AddEdge(i, j);
                        AddEdge(j, i);
                    }
                }
            }

            ans = min(ans, N - GetMatch());

        }, arr++N-));

        printf("%d\n", ans);

    }

__enTIME();;}

void __stTIME()
{
    #if _TIME
        START = clock();
    #endif
}

void __enTIME()
{
    #if _TIME
        END = clock();
        cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl;
    #endif
}

void __IOPUT()
{
    #if _INPUT
        freopen("in.txt", "r", stdin);
    #endif
    #if _OUTPUT
        freopen("out.txt", "w", stdout);
    #endif
}

相关文章