给定一个n的排列p,每次可以任意交换两个位置,花费为1,然后又给定m组交换,花费为0(可以任意次使用),问使该排列p有序的最小花费.(n<=18, m<=18)
做法
先考虑m=0,此时只要让每个数直接向目标位置交换即可,答案为n-环的个数再考虑m,既然可以任意交换,那就相当于这些位置是等价的,可以维护出每个等价的集合,然后直接全排列枚举每个集合,让p通过m=0的方式转换成该排列,最后取最小值.这样交的话其实只会tle一个点.如果某个集合的大小>10,全排列枚举显然t.但是我们并不需要枚举每个集合的排列,因为前几个数归位后,最后一个集合的数自然就归位了.所以我们不枚举最大的集合就可以了,这样我们枚举的集合的大小最多只有9,9!(362880)完全可以接受.
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
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 20;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, m, p[N], pos[N], x[N], y[N];
int tmpp[N];
int f[N], ans;
vector<vector<int>> vec;
vector<int> rt[N];
int find(int x)
{
if(x==f[x]) return x;
return f[x] = find(f[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if(x==y) return;
f[x] = y;
}
int cal()
{
int cnt = 0;
for(int i=1; i<=n; i++)
tmpp[i] = p[i];
for(int i=1; i<=n; i++)
{
int j = i;
while(pos[tmpp[j]]&&pos[tmpp[j]]!=j)
{
cnt++;
swap(tmpp[j], tmpp[pos[tmpp[j]]]);
}
}
return cnt;
}
void dfs(int x)
{
if(x==sz(vec))
{
ans = min(ans, cal());
return;
}
vector<int> idx(sz(vec[x]));
iota(all(idx), 0);
do {
for(int i=0; i<sz(vec[x]); i++)
pos[vec[x][i]] = vec[x][idx[i]];
dfs(x+1);
}while(next_permutation(all(idx)));
}
void solve()
{
scanf("%d%d", &n, &m);
ans = n - 1;
vec.clear();
for(int i=1; i<=n; i++)
{
scanf("%d", p+i);
f[i] = i;
pos[i] = 0;
rt[i].clear();
}
for(int i=1; i<=m; i++)
{
scanf("%d%d", x+i, y+i);
merge(x[i], y[i]);
}
int mx = 0;
for(int i=1; i<=n; i++)
{
int r = find(i);
rt[r].pb(i);
mx = max(mx, sz(rt[r]));
}
bool tag = 0;
for(int i=1; i<=n; i++)
if(f[i]==i && sz(rt[i])<mx) vec.pb(rt[i]);
else if(f[i]==i && sz(rt[i])==mx)
{
if(!tag) tag = 1;
else vec.pb(rt[i]);
}
dfs(0);
printf("%d\n", ans);
}
int main()
{
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
|