—— Summon, Light!
0%

hdu 5727 Necklace 全排列+二分图

发表于 更新于 Valine：

Necklace

题意：要用ｎ个阳石和ｎ个阴石来串一个项链（环），规定阳石旁边只能是阴石，阴石旁边只能是阳石，现在有 ｍ 对影响关系，x 号阳石与 y 号阴石相邻会使阳石变暗（照样可以用），问串这个项链最少让几个阳石变暗

题解：一看就是两个点集之间连边，瞬间想到二分图。但是后面其实并不好想。。。

首先发现 n 很小，即使是全排列的复杂度也能承受，那么我们可以枚举阴石的每一种排列，并且把阳石编号和阳石摆放位置作为两个点集匹配。用 $a[i]$ 表示第 $i$ 个阴石的编号，用 $g[i][j]$ 表示 $i$ 号阳石能否放在第 $j$ 个位置，这时就要考虑第 $i$ 个阴石和第 $i+1$ 个阴石对第 $i$ 个阳石是否有影响了，把没影响的连边，做一次二分图最大匹配，用 n-最大匹配 更新答案即可。
复杂度为 $O(N!\times N^{2})$ ，很容易TLE。。。
于是去查了查，发现有1个算法优化和2个常数优化。。。

  1. 在环的意义下，其实只有 $(n-1)!$ 种排列，比如：
    1 2 3 ... n
    n 1 2 ... n-1
    n-1 n 1 ... n-2
    这几种排列的答案一定是相等的
  2. ans=0 时已经找到最优解，可以直接退出
  3. 使用 next_permutation() 会比递归形式更快。

加了这些优化以后跑得飞快，只要400+ms。。。代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int N=12;
int a[N],b[N],link[N];
int g[N][N],mp[N][N];
bool used[N];
int n,m,ans;

bool dfs(int u)
{
    for (int v=1;v<=n;v++)
        if (g[u][v]&&!used[v]) {
            used[v]=true;
            if (link[v]==-1||dfs(link[v])) {
                link[v]=u;
                return true;
            }
        }
    return false;
}

int hungary()
{
    int res=0;
    memset(link,-1,sizeof(link));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) {
            g[i][j]=0;
            if (j==n) {
                if (!mp[i][a[j]]&&!mp[i][a[1]]) g[i][j]=1;
            } else {
                if (!mp[i][a[j]]&&!mp[i][a[j+1]]) g[i][j]=1;
            }
        }
    for (int i=1;i<=n;i++) {
        memset(used,0,sizeof(used));
        if (dfs(i)) res++;
    }
    return res;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (!n||!m) {
            puts("0");
            continue;
        }
        for (int i=1;i<=n;i++) a[i]=i;
        memset(mp,0,sizeof(mp));
        for (int i=1;i<=m;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            mp[x][y]=1;
        }
        ans=n;
        do {
            ans=min(ans,n-hungary());
            if (!ans) break;
        } while (next_permutation(a+2,a+n+1));
        printf("%d\n",ans);
    }
    return 0;
}
咖啡，亦我所需也