HDU5727 Necklace

2016多校, HDU, 搜索

　　2016 Multi-University Training Contest 1

　　题意：给定若干阴阳珠子交错排列成环，有些阳珠与特定的阴珠相邻时会褪色，求最少的褪色数。 - 原题链接

　　最开始的想法是二分图跑最佳匹配，想了好久确实没找到正确的转移…
　　官方题解是搜索＋估价剪枝，后来参考的是网上很多博客上的做法：固定阴珠，判断阳珠插入每一个位置的情况，若不褪色则连边，min（n-最大匹配）即最终答案。

  • 成环时可以固定一个位置，剩下的进行全排列，总方案为（n-1）!
  • next_permutation（）很实用，学习链接戳这儿 


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
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=9+5;
int n, m, a[maxn], dis, from[maxn];
bool br[maxn][maxn], st[maxn][maxn], vis[maxn];
void Init()
{
	memset(br, false, sizeof br);
	return ;
}
bool Dfs(int u)
{
	for(int i=1; i<=n; i++)
	{
		if(vis[i] || !st[u][i])	continue;
		vis[i]=true;
		if(!from[i] || Dfs(from[i]))
		{
			from[i]=u;
			return true;
		}
	}
	return false;
}
int main()
{
	while(scanf("%d%d", &n, &m)!=EOF)
	{
		if(!n)
		{
			printf("0\n");
			continue;
		}
		Init();
		for(int i=1, u, v; i<=m; i++)
		{
			scanf("%d%d", &u, &v);
			br[u][v]=true;
		}
		for(int i=1; i<=n; i++)	a[i]=i;
		int ans=n;
		do
		{
			memset(st, false, sizeof st);
			for(int i=1; i<=n; i++)
			{
				if(!br[i][a[1]] && !br[i][a[n]]) st[n][i]=true;
				for(int j=1; j<n; j++)
					if(!br[i][a[j]]&& !br[i][a[j+1]]) st[j][i]=true;
			}
			int tmp=0;
			memset(from, 0, sizeof from);
			for(int i=1; i<=n; i++)
			{
				memset(vis, false, sizeof vis);
				tmp+=Dfs(i);
			}
			ans=min(ans, n-tmp);
		}while(ans && next_permutation(a+1, a+1+n-1));
		printf("%d\n", ans);
	}
	return 0;
}