除了 dfs 枚举状态外，还可以直接循环利用 __builtin_popcount 枚举 $\left[0, 2^n\right)$ 中二进制下 $1$ 的个数为 $\dfrac{n}{2}$ 的状态，此时 $S$ 中的 $1$ 表示一个集合中的点，$\sim S$ 中前 $n$ 位的 $1$ 表示另一集合中的点，对于每个点 $u$ 计算与 $u$ 有边连接的点集和 $S$ 或 $\sim S$ （取决于 $u$ 是否在 $S$ 中）按位与后 $1$ 的个数，累加计算贡献。

int main() {
    dR(int, n, m);
    std::vector<int> e(n);
    while (m--) {
        dR(int, u, v), u--, v--;
        e[u] |= 1 << v;
        e[v] |= 1 << u;
    }
    int ans = 0, v = 1e9;
    for (int S = 0; S < (1 << n); S++)
        if (__builtin_popcount(S) == n >> 1) {
            int c = 0;
            for (int i = 0; i < n; i++)
                if (S & (1 << i))
                    c += __builtin_popcount(~S & e[i]);
                else
                    c += __builtin_popcount(S & e[i]);
            if (c < v)
                v = c, ans = S;
        }
    std::vector<int> a;
    for (int i = 0; i < n; i++)
        if (ans & (1 << i))
            a.push_back(i + 1);
    io.displayArray(a);
    return 0;
}

依旧模拟退火神力

思路

如果你知道每一个城市被分在了哪个国家，你可以在$O(M)$的复杂度判断具体需要多少个哨岗。注意到题目要求我们计算最好的情况下的划分方案，考虑模拟退火（还不会的出门左转）。我这里设置的处温是$1\times 10^4$，具体就是所有的划分情况（$2^N$）少一点，所以完全是可以过的。

总时间复杂度不详，反正是最烂解（整整108314ms啊）

AC代码

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=30;
const db e=1e-8;
struct node{int x,y;}a[N*N];
int n,m;
bool v[N],ansv[N];
int cal()
{
	int res=0;
	for(int i=1;i<=m;i++)if(v[a[i].x]^v[a[i].y])res++;
	return res;
}
int ans;
void SA()
{
	for(db s=1e4;s>e;s*=0.999)
	{
		int x=rand()%n+1,y=rand()%n+1;
		while(!(v[x]^v[y]))x=rand()%n+1,y=rand()%n+1;
		swap(v[x],v[y]);
		int res=cal();
		if(res<ans)
		{
			ans=res;
			for(int i=1;i<=n;i++)ansv[i]=v[i];
		}
		else if(exp((res-ans)/s)*RAND_MAX<rand())swap(v[x],v[y]);
	}
}
int main()
{
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=n/2;i++)v[i]=1;
	ans=0x3f3f3f3f;
	int testcnt=0;
	while(1.0*clock()/CLOCKS_PER_SEC<=2.4)SA(),testcnt++;
//	printf("%d\n",testcnt);
	for(int i=1;i<=n;i++)if(!(ansv[i]^ansv[1]))printf("%d ",i);
	return 0;
}

天哪，我这题调了好久啊，大约wa了18次……