自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:10:44，当前版本为作者最后更新于2025-03-11 19:01:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑在满足条件的图上，如果 $a$ 和 $b$ 不是朋友，它们和其它奶牛的关系：

• 如果 $c$ 和 $a$ 是朋友，根据要求 $b$ 要么和 $a$ 是朋友要么和 $c$ 是朋友，而 $a$ 和 $b$ 并不是朋友，所以 $b$ 和 $c$ 必须是朋友。
• 同理，如果 $c$ 和 $a$ 不是朋友，通过反证法可以证明 $b$ 和 $c$ 也不能是朋友。

那么，考虑满足条件的图的补图，不难发现它是由若干个团组成的。

这样，先把刚开始的图变成其补图，原问题就可以转化成：给定一个图，每次可以加边或删边，求将其变为若干个团的并的最少操作次数。

数据范围提示我们状压 DP。首先可以想到一个大致的思路：

设 $f_{S}$ 表示选择 $S$ 中的奶牛，它们内部合法（即形成若干个团）的最少操作次数。为了帮助转移，再设一个 $g_{S}$ 表示选择 $S$ 的奶牛，它们内部要连成一个团的最少操作次数（这个可以 $O(n^22^n)$ 预处理）。那么有：

$$f_{S}=\min\limits_{T\subset S}(f_{T}+g_{S\backslash T}) $$

涉及枚举子集，dp 时间复杂度 $O(3^n)$，总时间复杂度 $O(n^22^n+3^n)$。

但是需要注意实现细节：仔细想想，会发现直接这样转移，不管 $f_S$ 和 $g_S$ 是否需要包括内部的点连到外面的点的状态，总是会有一些边要么被重复算了，要么没有被计算进来。其实这不难解决，因为每条边就算要算，也最多被两个端点各算一次，所以只要保证在计算 $g_S$ 时，把集合内部的点之间的连边也算两次，最后把答案除以二就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=18;
bool a[N][N];
int f[1<<N],g[1<<N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=1;
	while(m--){
		int x,y;cin>>x>>y;
		a[x][y]=a[y][x]=0;//补图
	}
	for(int S=0;S<(1<<n);S++){
		for(int i=1;i<=n;i++)if((S>>(i-1))&1){
			for(int j=1;j<=n;j++){
				if(i!=j)g[S]+=(((S>>(j-1))&1)/*是否需要有边*/?(!a[i][j]):a[i][j]);
			}
		}
	}
	for(int S=0;S<(1<<n);S++){
		f[S]=g[S];
		for(int s=S;s;s=S&(s-1)){
			f[S]=min(f[S],f[S^s]+g[s]);
		}
	}
	cout<<f[(1<<n)-1]/2;
	return 0;
}