HDU 5727 Necklace(二分图最大匹配)

题意:

$给定2\times N个珠子的环,其中N个为yang,N个为yin,N\le 9$
$给定M\le N\times N个限制关系$
$对于每个限制关系a_i, b_i,表示yang a_i会变暗如果与yin b_i相邻$
$求最少的暗淡yang珠子数$

分析:

$由于是环,所以固定第1个珠子为1,然后8!枚举yin珠子的排列$
$之后对于每2个yin珠子的间隔,与yang珠子建图,表示这个yang珠子不会暗淡$
$跑二分图匹配,最大匹配数就是最大的不会暗淡的$
$ans=n-maxMatch$
$实际上匈牙利很快,然后如果都不暗淡提前退出就可以过去了$
$集训队的不带剪枝都过去了,不知道为啥窝自带百倍常数$
$时间复杂度O(8!\times nm)$

代码:

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//
// Created by TaoSama on 2016-07-20
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 10 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
int conflict[N][N];
struct Edge {
int v, nxt;
} edge[N * N];
int head[N], cnt;
void addEdge(int u, int v) {
edge[cnt] = {v, head[u]};
head[u] = cnt++;
}
int match[N], vis[N];
bool dfs(int u) {
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(vis[v]) continue;
vis[v] = true;
if(match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int hungary() {
int matches = 0;
memset(match, -1, sizeof match);
for(int i = 1; i <= n; ++i) {
memset(vis, 0, sizeof vis);
matches += dfs(i);
}
return matches;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
clock_t _ = clock();
while(scanf("%d%d", &n, &m) == 2) {
memset(conflict, 0, sizeof conflict);
for(int i = 1; i <= m; ++i) {
int u, v; scanf("%d%d", &u, &v);
conflict[u][v] = 1; //yang yin
}
int ans = -INF;
//yin
int ord[N]; ord[n + 1] = 1;
for(int i = 1; i <= n; ++i) ord[i] = i;
do {
// for(int i = 1; i <= n + 1; ++i) printf("%d ", ord[i]); puts("");
cnt = 0; memset(head, -1, sizeof head);
for(int i = 1; i <= n; ++i) { //gap
int l = ord[i], r = ord[i + 1];
for(int j = 1; j <= n; ++j) { //yang
if(conflict[j][l] || conflict[j][r]) continue;
// printf("%d, %d\n", i, j);
addEdge(i, j);
}
}
if(cnt <= ans) continue;
ans = max(ans, hungary());
if(ans == n) break;
} while(next_permutation(ord + 2, ord + n + 1));
printf("%d\n", n - ans);
}
#ifdef LOCAL
printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
#endif
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到