洛谷P3959.宝藏

题目大意

一个 \(n(1\leq n\leq 12)\) 个节点， \(m(0\leq m\leq 1000)\) 条边的无向图。每条边有一个权值 \(w_{i}（w_{i}\leq5\times10^5)\) 。可以选择图中任意一个节点，从这个节点开始，可以在图上对边进行扩展，知道所有的节点都被联通。每条边扩展所需要的费用是其权值 \(w_{i}\) 乘上这条边终点处的节点到初始节点的路径中所经过节点的数量（包括两端），求满足要求所需的最小花费。

思路

可以看出，最后所扩展的边和所有的节点一定构成一颗以初始节点为根的树，否则一定不会更优。之后可以考虑这颗树是逐层扩展而来，可以用一个集合来记录当前层数下每个节点是否被扩展到，然后可以进行动态规划，从 \(i-1\) 层到 \(i\) 层进行转移，于是设 \(dp[i,j]\) 为扩展到了第 \(i\) 层，当前以扩展到的节点状态为 \(j\) 的情况下的最小花费。设当状态 \(k\) 一次可扩展到的最大状态为 \(k'\) ，从 \(k\) 扩展到 \(j\) 的最小花费为 \(c\) ,于是当 \(j\) 为 \(k'\) 的一个子集，并且 \(k\) 为 \(j\) 的一个子集时，可以进行转移：

最开始所有的 \(dp[1,1< 为 \(0\) ，其余为 \(inf\) ，最后答案取 \(min\{dp[i,(1< , 其中合法的转移状态 \(k\) ，扩展所需的最小花费 \(c\) 都可以预处理出来，并且在转移的时候不必考虑是否是由 \(k\) 中的 \(i-1\) 层节点还是其他节点转移到 \(i\) 层节点，转移是都按 \(\times(i-1)\) 来计算即可，因为某一条路径如果可以以比 \(i-1\) 更小的系数被扩展到，其答案也被其他状态记录下来，按上述方法计算得到的答案一定会更大，从而不影响最小值的计算，复杂度 \(O(n3^{n}+m2^{n})\)

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 15;

int N, M;
struct edge {
	int to, cost;
};
vectorG[maxn];
int dp[maxn][1 << 13];
int ex[1 << 13], to[maxn];
int r[1 << 13][maxn];

void add_edge(int from, int to, int cost)
{
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

void solve()
{
	memset(r, inf, sizeof(r));
	for (int i = 0; i < (1 << N); i++)
	{
		ex[i] = i;
		for (int j = 0; j < N; j++)
		{
			if ((i >> j) & 1)
			{
				int v = j + 1;
				for (int k = 0; k < G[v].size(); k++)
				{
					edge& e = G[v][k];
					r[i][e.to] = min(r[i][e.to], e.cost);
				}
				ex[i] |= to[j + 1];
			}
		}
	}
	memset(dp, inf, sizeof(dp));
	for (int i = 0; i < N; i++)
		dp[1][1 << i] = 0;
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j < (1 << N); j++)
		{
			int k = j;
			do
			{
				if ((j & ex[k]) == j)
				{
					int c = 0;
					for (int l = 0; l < N; l++)
					{
						if (((((j >> l) & 1) ^ ((k >> l)) & 1)) == 1)
							c += r[k][l + 1];
					}
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + (i - 1) * c);
				}
				k = (k - 1) & j;
			} while (k != j);
		}
	}
	int ans = inf;
	for (int i = 1; i <= N; i++)
		ans = min(ans, dp[i][(1 << N) - 1]);
	cout << ans << endl;
}

int main()
{
	IOS;
	cin >> N >> M;
	int u, v, w;
	for (int i = 1; i <= M; i++)
	{
		cin >> u >> v >> w;
		to[u] |= (1 << (v - 1));
		to[v] |= (1 << (u - 1));
		add_edge(u, v, w);
	}
	solve();

	return 0;
}