Necklace

题意:要用n个阳石和n个阴石来串一个项链(环),规定阳石旁边只能是阴石,阴石旁边只能是阳石,现在有 m 对影响关系,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;
}