这道题考场上我想到的居然是最小生成树（于是就成功的爆零了），如果加了特判的话就有80分，主要还是数据太水了吧。

下面就来讲讲正解呗，因为之前接触过状压DP，所以做起来还是比较顺。

一个二进制数\(0000\)表示4个水杯都装有水，\(0001\)表示第一个水杯是空的，代价最小的状态，同理，\(1000\)表示第4个水杯是空的，代价最小的状态。

现在来考虑状态转移，拿\(1000\)举例，不难发现它可以转移到。

\(1100\)
\(1010\)
\(1001\)

（可以这么考虑，我们在\(1000\)这个状态下进行了一个将\(i\)杯子的水倒入了\(j\)的操作。不管\(i\)和\(j\)是多少，总会有一个杯子会空掉，所以会多出一个"1"出来）

因为每次操作只能在两个装有水的杯子\(i\)和\(j\)的杯子进行，所以我们只需要在当前状态\(1000\)里暴力枚举位数为\(0\)的\(i\)和\(j\),模拟将\(i\)倒入\(j\)的操作。因为\(i\)倒入了\(j\)，所以第\(i\)位为1，权值为\(w_{ij}\)。

那么我们便可以得出状态转移方程：

\(f_{S+1<<i} = min(f_{S}+w_{ij})\)

S为当前状态，一个二进制数。当空的杯子，也就是S的1的个数为\(n-k\)时，我们便可以记录答案。

代码

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define N 30

int n,k,w[N][N],ans,inf,f[1<<21];

int main() {

	memset(f,0x3f,sizeof(f));

	ans=f[0];

	cin>>n>>k;

	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)

		cin>>w[i][j];

	f[0]=0;

	for(int S=0;S<1<<n;S++) {

		int sum=0;

		for(int i=1;i<=n;i++) if(S & (1<<(i-1))) sum++;

		if(sum==n-k) {

			ans=min(ans,f[S]);

			continue;

		}

		if(sum>n-k) continue;

		for(int i=1;i<=n;i++)

			if(!(S&(1<<(i-1))))

				for(int j=1;j<=n;j++)

					if(!(S & (1<<(j-1))) && i!=j)

						f[S+(1<<(i-1))]=min(f[S+(1<<(i-1))],f[S]+w[i][j]);

	}

	cout<<ans;

}

ij

模拟赛毒瘤状压DP题：Kronican

代码