题目大意
给定两个长度为 \(n(n\leq16)\) 的数组 \(a\) 和 \(b\)，可以进行若干次如下操作：
- 选择两个数 \(i,j(1\leq i,j \leq n)\)，将（\(a_i\) 或 \(b_i\)）与（\(a_j\) 或 \(b_j\)）交换。
问最少进行多少次上述操作，可使得对于每个 \(i \in [1,n]\)，都有 \(|a_i-b_i|\leq c\)。
问题转化
首先我们用状态压缩的思想，用状态的第 \(i\) 位表示 是（\(1\)）否（\(0\)）有 \(|a_i-b_i|\leq c\)。
我们可以把一个个状态都看作点，如果两个状态之间可以通过调换牙刷互相得到，那么这两个点间就有一条边。
和 在边权相同的图上可以直接用 \(\operatorname{BFS}\) 求单源最短路 同样的道理，这样在建出的图上跑一遍 \(\operatorname{BFS}\) 即可，起点是初始状态。
但是到达每个点时的\(a\) 数组和 \(b\) 数组会互不相同，所以我们用 \(a1[i][j]\) 和 \(b1[i][j]\) 记录到达点 \(i\)（状态为 \(i\)）时，第 \(j\) 把牙刷的两个属性值，这样的话就可以根据 \(a1\) 和 \(b1\) 判断两个点之间是否能互相到达。
我们并不需要真正地去建图，真正去建图的话很麻烦。可以在 \(\operatorname{BFS}\) 的过程中，对于当前（队头）的状态，枚举交换哪两个，然后让交换后的状态入队即可。
\(\operatorname{DP}\)求解
至于 \(\operatorname{BFS}\) 中的 \(\operatorname{DP}\) 部分（求最短路，但还是更像状压 \(\operatorname{DP}\) 一点），状态转移方程如下：
设 \(mask\) 为当前状态，\(flag_i\) 表示 是（\(1\)）否（\(0\)）有 \(|a_i-b_i|\leq c\)，\(dp_i\) 表示到达状态 \(i\) 至少要交换几次。
现在对 \((i,j)\) 进行交换操作
-
若交换后 \(flag_i\) 发生改变，而 \(flag_j\) 未发生改变，则
dp[mask^(1<<i)]=dp[mask]+1。 -
若交换后 \(flag_j\) 发生改变，而 \(flag_i\) 未发生改变，则
dp[mask^(1<<j)]=dp[mask]+1。 -
若交换后 \(flag_j\) 和 \(flag_j\) 均发生改变，则
dp[mask^(1<<i)^(1<<j)]=dp[mask]+1。
那么如何判断交换后 \(flag_i\) 和 \(flag_j\) 是否发生变化呢？
比如交换 \(a_i\) 和 \(a_j\)，若(abs(a1[mask][i]-b1[mask][i])<=c)^(abs(a1[mask][j]-b1[mask][i])<=c)==1，则 \(flag_i\) 发生变化。同样的，若(abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][i]-b1[mask][j])<=c)==1，则 \(flag_j\) 发生变化。
那么如果交换 \(a_i\) 和 \(b_j\)，若(abs(a1[mask][i]-b1[mask][i])<=c)^(abs(b1[mask][j]-b1[mask][i])<=c)==1，则 \(flag_i\) 发生变化。同样的，若(abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][j]-a1[mask][i])<=c)==1，则 \(flag_j\) 发生变化。
不难发现，讨论以上两种情况其实就足够了，没必要再用 \(a_j\) 去交换。
举个例子，\(a_i=1,b_i=2,a_j=3,b_j=4\)。那么上面的第一种实质上是让 \(1,4\) 一组，\(2,3\) 一组。第二种是让 \(1,3\) 一组，\(2,4\) 一组。此时就已经包含了所有的情况了，不需要让 \(2\) 去和 \(3\) 或 \(4\) 交换。
代码如下：
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define reg register
using namespace std;
inline int read()
{
int x=0;
short f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,c,dp[1<<20],a[20],b[20],a1[1<<20][20],b1[1<<20][20],mask;
bool vis[1<<20];
inline void memcopy(int x) {for(reg int i=0;i<n;i=-~i) a1[x][i]=a1[mask][i],b1[x][i]=b1[mask][i];}
inline void DP()
{
queue<int>q;
q.push(mask);
while(!q.empty()&&!dp[(1<<n)-1])//小优化，如果dp[(1<<n)-1]已被求出就直接结束
{
mask=q.front();
q.pop();
for(reg int i=0;i<n;i=-~i/*位运算的i++*/)
for(reg int j=0;j<i;j=-~j)//i和j 枚举交换哪两个
{
int nxt1=mask^(1<<j),nxt2=mask^(1<<i),nxt3=mask^(1<<i)^(1<<j);
if((abs(a1[mask][i]-b1[mask][i])<=c)^(abs(a1[mask][j]-b1[mask][i])<=c))//flag[i]发生变化
{
if((abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][i]-b1[mask][j])<=c))//flag[j]发生变化
{
if(!vis[nxt3])
{
dp[nxt3]=dp[mask]+1;vis[nxt3]=1;q.push(nxt3);
memcopy(nxt3);swap(a1[nxt3][i],a1[nxt3][j]);
//flag[i]和flag[j]均发生变化
}
}
else if(!vis[nxt2])
{
dp[nxt2]=dp[mask]+1;vis[nxt2]=1;q.push(nxt2);
memcopy(nxt2);swap(a1[nxt2][i],a1[nxt2][j]);
//仅flag[i]发生变化
}
}
else if((abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][i]-b1[mask][j])<=c)&&!vis[nxt1])//flag[j]发生变化
{
dp[nxt1]=dp[mask]+1;vis[nxt1]=1;q.push(nxt1);
memcopy(nxt1);swap(a1[nxt1][i],a1[nxt1][j]);
//仅flag[j]发生变化
}
//1.exchange a[i] and a[j]
if((abs(a1[mask][i]-b1[mask][i])<=c)^(abs(b1[mask][j]-b1[mask][i])<=c))
{
if((abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][j]-a1[mask][i])<=c))
{
if(!vis[nxt3])
{
dp[nxt3]=dp[mask]+1;vis[nxt3]=1;q.push(nxt3);
memcopy(nxt3);swap(a1[nxt3][i],b1[nxt3][j]);
}
}
else if(!vis[nxt2])
{
dp[nxt2]=dp[mask]+1;vis[nxt2]=1;q.push(nxt2);
memcopy(nxt2);swap(a1[nxt2][i],b1[nxt2][j]);
}
}
else if((abs(a1[mask][j]-b1[mask][j])<=c)^(abs(a1[mask][j]-a1[mask][i])<=c)&&!vis[nxt1])
{
dp[nxt1]=dp[mask]+1;vis[nxt1]=1;q.push(nxt1);
memcopy(nxt1);swap(a1[nxt1][i],b1[nxt1][j]);
}
//2.exchange a[i] and b[j]
}
}
}
signed main()
{
n=read();c=read();
for(reg int i=0;i<n;i=-~i)
{
a[i]=read();b[i]=read();
if(abs(a[i]-b[i])<=c) mask|=(1<<i);
}
dp[mask]=0;vis[mask]=1;
for(reg int i=0;i<n;i=-~i) a1[mask][i]=a[i],b1[mask][i]=b[i];
DP();
return printf("%d",dp[(1<<n)-1]),0;
}
时间复杂度
\(\operatorname{BFS}:2^n\)。
枚举交换哪两个（\(i=0\sim n-1,j=0\sim i-1\)）\(:1+2+...+(n-1)=n(n-1)/2\)。
将原来的所对应的属性值数组 赋值给 交换后的所对应的属性值数组 \(:n\)。
总复杂度 \(:O(2^n\cdot(n(n-1)/2+n))\)，化简得 \(O(2^{n-1}\cdot n(n+1))\)，约 \(O(2^{n-1}\cdot n^2)\)，完全能过。
但实际复杂度是达不到的，因为几乎不会出现 每个状态都能到达 的情况，而且我们还有小优化。