算法

20pts

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 15;

int n, m;
vector<pair<int, int>> g[MAXN]; // 邻接表存树
int depth[MAXN]; // 每个节点的深度
long long ans = INF;

// DFS计算以root为根时，从root到每个节点的深度
void dfs(int u, int fa, int d) {
    depth[u] = d;
    for (auto [v, w] : g[u]) {
        if (v == fa) continue;
        dfs(v, u, d + 1);
    }
}

// 计算以root为根的代价
long long calc(int root) {
    // 先计算每个节点的深度
    dfs(root, -1, 0);
    
    long long total = 0;
    // 遍历每条边，计算代价
    for (int u = 0; u < n; u++) {
        for (auto [v, w] : g[u]) {
            if (u < v) { // 每条边只计算一次
                // 深度较小的节点是父节点，深度较大的节点是子节点
                int child = (depth[u] > depth[v]) ? u : v;
                total += 1LL * w * depth[child];
            }
        }
    }
    return total;
}

int main() {
    cin >> n >> m;
    
    // 读入树的边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    // 枚举每个节点作为根
    for (int root = 0; root < n; root++) {
        ans = min(ans, calc(root));
    }
    
    cout << ans << endl;
    return 0;
}

60pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int N = 2500 + 10;
int g[N][N], dep[N];
bool st[N];
vector<pair<int, int>>e[N];
int sum = 0;
int ans = 1e9;
void dfs(int cnt) {
	if (sum >= ans)return;
	if (cnt == n) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!st[i])continue;
		for (int j = 1; j <= n; j++) {
			if (st[j]||g[i][j]>=1e9)continue;
			st[j] = 1;
			dep[j]=dep[i]+1;
			sum += g[i][j] * dep[i];
			dfs(cnt+1);
			sum -= g[i][j] * dep[i];
			st[j] = 0;
			dep[j]=0;
		}
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	for(int i=1;i<=n;i++){
		dep[i]=1;
		st[i]=1;
		sum=0;
		dfs(1);
		dep[i]=0;
		st[i]=0;
	}
	cout << ans;
	return 0;
}

100pts

(状态压缩DP) $O(n^2 3^n)$

状态压缩DP，下文中 i 是一个 n 位二进制数，表示每个点是否存在。

状态定义：

• f[i][j] 表示：
  • 集合：所有包含 i 中所有点，且树的高度等于 j 的生成树。
  • 属性：最小花费。

状态计算：

枚举 i 的所有非全集子集 S 作为前 j - 1 层的点，剩余点作为第 j 层的点。

核心：

求出第 j 层的所有点到 S 的最短边，将这些边权和乘以 j，直接加到 f[S][j - 1] 上，即可求出 f[i][j]。

证明：

将这样求出的结果记为 f'[i][j]。

• f[i][j] 中花费最小的生成树一定可以被枚举到，因此 f[i][j] >= f'[i][j]。
• 如果第 j 层中用到的某条边 (a, b) 应该在比 j 小的层，假设 a 是 S 中的点，b 是第 j 层的点，则在枚举 S + {b} 时会得到更小的花费，即这种方式枚举到的所有花费均大于等于某个合法生成树的花费，因此 f[i][j] <= f'[i][j]。

所以有 f[i][j] = f'[i][j]。

时间复杂度

包含 $k$ 个元素的集合有 $C(n, k)$ 个，且每个集合有 $2^k$ 个子集，因此总共有 $C(n, k) * 2^k$ 个子集。$k$ 可以取 $0∼n$，则总共有 = $3^n$，这一步由二项式定理可得。

对于每个子集需要 $n^2$ 次计算来算出剩余点到子集中的最短边。

因此总时间复杂度是 O($n^2 * 3^n$)。

#include<bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N,INF=0x3f3f3f3f;
int n,m;
int d[N][N],g[N][M]; //d[i][j]表示i到j的最短距离,g[i][j]表示i点到j集合中的距离 
int f[M][N]; //f[i][j] 表示点集i一共j层的最小值 
int main()
{
	cin>>n>>m;
	memset(d,0x3f,sizeof d);
	for(int i=0;i<n;i++) d[i][i]=0;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		d[a][b]=d[b][a]=min(d[a][b],c); //去重得到最小距离 
	}
	memset(g,0x3f,sizeof g);//初始化距离
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<1<<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				if(j>>k&1) //说明j集合中包含k点 
				{
					g[i][j]=min(g[i][j],d[i][k]) ;//更新i到j集合的距离 
				}		
			}
		}	
	} 
	memset(f,0x3f,sizeof f); //初始化 
	for(int i=0;i<n;i++) //初始化每个点为根 
	{
		f[1<<i][0]=0;
	}
	for(int i=1;i<1<<n;i++) //枚举所有情况 
	{
		for(int j=i-1&i;j;j=j-1&i) //枚举所有子集 
		{
			int r=i^j;//剩余部分(在j-1层) 
			int cost=0;
			for(int k=0;k<n;k++)
			{
				if(j>>k&1)
				{
					cost+=g[k][r];	
					if(cost>=INF) break; 
				}	
			} 
			if(cost>=INF) continue;
			for(int k=1;k<n;k++) //枚举前面的最小值 
			{
				f[i][k]=min(f[i][k],f[r][k-1]+cost*k); //当前放到哪一层 
			}
		}
	}
	int res=INF;
	for(int i=0;i<n;i++) //枚举所有点在前i层 
	{
		res=min(res,f[(1<<n)-1][i]);
	}
	cout<<res;
	return 0;
}