最小生成树
定义：在无向图\(G=(V,E)\)中，一颗连接所有节点的树(无根树)被称为这个无向图的生成树，其中边权之和最小的那一颗被称为最小生成树
定理：最小生成树一定包含无向图中权值最小的边
证明：
反证法，假设无向图G=(V,E)存在一颗最小生成树不包含权值最小的边，把这条边加入最小生成树集合之后会形成一个环，这个环上任意一条边都比新加入的边的权值大，任意断开一条可以得到一个权值和更小的生成树，假设不成立，故命题成立
推论：
给定一张无向图\(G=(V,E),n=|V|,m=|E|\)从\(E\)中选出\(k Kruskal算法 \(Kruskal\)算法就是基于上述推论的。\(Kruskal\)算法总是维护无向图的最小生成森林，最初可以认为生成森林是由零条边构成，每个节点各自构成一颗仅包含一个节点的树 在任意时刻\(Kruskal\)算法从剩余的边中选出一条权值最小的，并把这条边的两个端点属于的生成树连通，图中节点的连接情况可以用并查集维护 详细的说，步骤如下 建立并查集，每个点各自构成一个集合 把所有边按权值从小到大排序，依次扫描每一条边\((u,v,w)\) 如果\(u,v\)属于同一集合，忽略，继续扫描下一条 将答案累加上\(w\)，并合并\(u,v\)所在集合 重复3.4直到所有边扫描完成 时间复杂度为\(O(m\log m)\) struct node{ int u,v,w; bool operator<(const node b)const{ w } }a[100005]; int f[100005],n,m,ans; int find(int x){return x==f[x]?x:f[x]=find(f[x]);} int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); sort(a+1,a+m+1); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++){ int u=find(a[i].u),v=find(a[i].v); if(u==v)continue; f[u]=v; ans+=a[i].w; } printf("%d",ans); } Prim \(Prim\)同样基于推论，与\(Kruskal\)不同的是，\(prim\)算法始终维护最小生成树的一部分，不断扩大这个部分，最终扩展为一颗最小生成树 我们设\(S\)表示我们维护的最小生成树集合，\(T\)表示剩余节点集合，我们每一次需要找到一条边，两个端点分属两个集合且边权最小，然后将这条边累计上答案，属于\(T\)的那个端点加入到\(S\)中，直到\(|S|=|V|\) 在具体实现中，最初\(S\)中只有一号节点，我们维护一个数组\(d\)，对于每个节点\(x\)，若\(x\in S\)，则\(d[x]\)表示\(x\)加入\(S\)时所连接的最小边的权值，若\(x\in T\)，则\(d[x]\)表示\(x\)与\(S\)中节点相连的最小边权 类比\(Dijkstra\)算法，我们也对其进行更新操作，用数组\(vis\)标记节点是否属于\(S\)，然后找到不属于\(S\)的节点的\(d\)值最小的，将其加入\(S\)，并且累计答案，然后这个节点对其所有出边且属于\(T\)的节点进行更新操作，直到所有节点更新完毕 时间复杂度为\(O(n^2)\)可以使用二叉堆优化为\(O(m\log n )\)，但这就不如\(Kruskal\)算法了，代码复杂度和常数复杂度都是 由于\(prim\)算法的时间复杂度仅与节点个数有关，所以常用于稠密图尤其是完全图的最小生成树求解 int prim(){ memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); d[1]=0; for(int i=1;i int num=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&(num==-1||d[num]>d[j]))num=j; } vis[num]=1; for(int j=1;j<=n;j++){ if(!vis[j])d[j]=min(d[j],a[num][j]); } } for(int i=2;i<=n;i++)ans+=d[i]; return ans; } 因为\(d\)数组的定义，于是\(\sum_{i=1}^nd[i]\)就是答案 最小生成树的应用 例题1:北极网络 国防部（DND）希望通过无线网络连接几个北部前哨站。 在建立网络时将使用两种不同的通信技术：每个前哨站都有一个无线电收发器，一些前哨站还有一个通信卫星。 任意两个拥有通信卫星的前哨站不论它们的位置如何，都可以通过卫星进行通信。 而如果利用无线电进行通信，则需要两个前哨站的距离不能超过 \(D\) 方可进行通信。 而 \(D\) 的大小取决于收发器的功率，收发器的功率越大，\(D\) 也就越大，但是需要的成本也就越高。 出于采购和维护的考虑，所有的前哨站都采用相同的收发器，也就是说所有前哨站的无线电通信距离 \(D\) 都是相同的。 你需要确定在保证任意两个前哨站之间都能进行通信（直接或间接）的情况下，\(D\) 的最小值是多少。 输入格式 第一行包含整数 \(N\)，表示共有 \(N\) 组测试数据。 每组数据的第一行包含两个整数 \(S\) 和 \(P\)，其中 \(S\) 为卫星个数，\(P\) 为前哨站个数。 接下来 \(P\) 行每行包含两个整数 \(x\) 和 \(y\)，分别表示一个前哨站的横纵坐标。 输出格式 输出一个实数，表示 \(D\) 的最小值，结果保留两位小数。 数据范围 \(1≤S≤100,\) \(S≤P≤500,\) \(0≤x,y≤10000\) 分析： 首先这道题是一个完全图，我们需要对每一个前哨站互相连边 算法1：二分答案 单调性很容易发现,\(D\)更大肯定比\(D\)更小使得可以通信的前哨站更多，于是我们可以二分答案，设当前二分的值是\(mid\),我们将边权大于\(mid\)的边赋值为\(1\)，小于\(mid\)的边赋值为0，很明显，我们假设所有边权为\(0\)的边所连接到的点构成的若干个连通块，而我们的卫星可以使得连通块相连，即对每一个连通块安装一个卫星，就可以连通整张图，于是我们只需要统计连通块的个数，与\(S\)相比较即可确定二分上下界变化，对于连通块的求解需要使用并查集维护 const int N = 510; const double eps = 1e-4; int n, m, x[N], y[N], fa[N]; double d[N][N]; int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); } bool check(double now) { for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) if (d[i][j] <= now) fa[findfa(i)] = findfa(j); int sum = 0; for (int i = 1; i <= n; i++) if (fa[i] == i) sum++; return sum <= m; } int main() { int tt; cin >> tt; while (tt--) { cin >> m >> n; for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]); for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) d[i][j] = (double)sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); double l = 0.0, r = 14145.0, mid; while (l + eps < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } printf("%.2lf\n", r); } return 0; } 算法2：\(Kruskal\) 由上文推论，在本题中，我们实质上需要维护最小生成树的一个子图，满足子图上最大边的边权不超过\(D\)，由推论性质得到，我们最小生成树有\(P-1\)条边，而卫星可以使得\(S-1\)条边不计入，于是我们只需要统计最小生成树里第\(P-1-(S-1)=P-S\)大的边的边权就是答案 int p,s,f[100005],cnt,vis[100005],m; struct node{ int len,u,v; bool operator<(const node b)const{ return len } }a[1000005]; pair int get(pair return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } void init(){ m=0; scanf("%d%d",&s,&p); for(int i=1;i<=p;i++)scanf("%d%d",&in[i].first,&in[i].second); for(int i=1;i<=p;i++){ for(int j=i+1;j<=p;j++){ a[++m]={get(in[i],in[j]),i,j}; } } sort(a+1,a+m+1); } int Kruskal(){ memset(vis,0,sizeof vis); for(int i=1;i<=p;i++)f[i]=i; cnt=0; for(int i=1;i<=m;i++){ int u=a[i].u,v=a[i].v; u=find(u),v=find(v); if(v==u)continue; if(++cnt==p-s)return a[i].len; f[u]=v; } } int main(){ freopen("1.in","r",stdin); int n; scanf("%d",&n); while(n--){ init(); printf("%.2f",sqrt(Kruskal())); // for(int i=1;i<=m;i++)printf("%.3f ",sqrt(a[i].len)); puts(""); } } 算法1的时间复杂度是\(O(n^2\log V)\),算法2的时间复杂度是\(O(n^2\log n)\)，理论上讲算法2更优 这道题启发我们： 1.发掘题目单调性，使用二分判定答案 2.考虑Kruskal和prim思想的本质，理解最小生成树定理 例题2:沙漠之王 简单的说题意，就是求最优比率生成树，即每条边有成本\(cost\)和长度\(len\)，要求\(\frac{\sum cost}{\sum len}\)的最小值 很明显，这是一道0/1分数规划与最小生成树的综合题 我们只需要建立一张图，每个边的权值是\(cost_i-mid\times len_i\),对这张图求最小生成树，若边权和非负0则令\(l=mid\),否则令\(r=mid\) 为什么是最小生成树而不是最大生成树呢？因为只有取最小生成树的时候，我们满足这张图其余生成树的答案一定不小于最小生成树的比率，否则就可以继续减小(这里蓝书上出错了) double cost[1005][1005];int n,vis[1005]; double d[1005][1005],dis[1005]; double b[1005][1005]; struct node{ int x,y,h; }a[1005]; double get(node a,node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void init(){ for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ cost[i][j]=cost[j][i]=get(a[i],a[j]); d[i][j]=d[j][i]=abs(a[i].h-a[j].h); } } } bool check(double mid){ // printf("%.5f\n",mid); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ if(i==j){ b[i][j]=2e9; continue; } b[i][j]=b[j][i]=d[i][j]-mid*cost[i][j]; // printf("%.5f ",b[i][j]); } // puts(""); } memset(vis,0,sizeof vis); for(int i=1;i<=n;i++)dis[i]=2e9; dis[1]=0; for(int i=1;i double now;int id=0; for(int j=1;j<=n;j++){ if(!vis[j]&&(id==0||(now>dis[j])))id=j,now=dis[j]; } // printf("%d\n",id); vis[id]=1; for(int j=1;j<=n;j++){ if(!vis[j]){ // printf("A%d %.4f ",j,dis[j]); dis[j]=min(dis[j],b[id][j]); // printf("%.4f\n",dis[j]); } } } double ans=0; for(int i=2;i<=n;i++)ans+=dis[i]; //printf("%.3f\n",ans); return ans>=0; } int main(){ //freopen("10.in","r",stdin); while(~scanf("%d",&n)&&n){ for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].h); } init(); double l=0,r=50; while(r-l>1e-8){ double mid=(l+r)/2; if(check(mid))l=mid; else r=mid; } printf("%.3f\n",(l+r)/2); } } 这道题是最优比率生成树模型，非常重要 例题3:黑暗城堡 在顺利攻破 \(Lordlsp\) 的防线之后，\(lqr\) 一行人来到了 \(Lordlsp\) 的城堡下方。 \(Lord lsp\) 黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。 现在 \(lqr\) 已经搞清楚黑暗城堡有 \(N\) 个房间，\(M\) 条可以制造的双向通道，以及每条通道的长度。 \(lqr\) 深知 \(Lord lsp\) 的想法，为了避免每次都要琢磨两个房间之间的最短路径，\(Lord lsp\) 一定会把城堡修建成树形的。 但是，为了尽量提高自己的移动效率,\(Lord lsp\) 一定会使得城堡满足下面的条件： 设 \(D[i]\) 为如果所有的通道都被修建，第 \(i\) 号房间与第 \(1\) 号房间的最短路径长度；而 \(S[i]\) 为实际修建的树形城堡中第\(i\) 号房间与第 \(1\) 号房间的路径长度；要求对于所有整数 \(i\)，有 \(S[i]=D[i]\) 成立 。 为了打败 \(Lord lsp\)，\(lqr\) 想知道有多少种不同的城堡修建方案。 你需要输出答案对 \(2^31–1\) 取模之后的结果。 输入格式 第一行有两个整数 \(N\) 和 \(M\)。 之后 \(M\) 行，每行三个整数 \(X\)，\(Y\) 和\(L\)，表示可以修建 \(X\) 和 \(Y\) 之间的一条长度为 \(L\) 的通道。 输出格式 一个整数，表示答案对 231–1 取模之后的结果。 数据范围 \(2≤N≤1000,\) \(N−1≤M≤N(N−1)/2,\) \(1≤L≤100\) 简单来说，本题让我们统计在一张无向图里有多少最短路径生成树，最短路径生成树是指对于任意边\((u,v,w)\)都有\(D[u]+u=D[v]\) 我们可以先使用\(Dijkstra\)求出D数组，然后统计\(\forall v\in[1,n]\)有多少个\(u\)满足\(D[u]+w_{u,v}=D[v]\)，记为\(cnt_v\)，最后把所有的cnt乘起来即可，至于原因，因为正权图的原因，对于cnt的计算可以使用对D从小到大排序之后按顺序统计，由于数据较小我就直接上\(n^2\)了其实是我没调好 正确性证明：很明显，当\(u\)满足\(D[u]+w_{u,v}=D[v]\)，此时从v连接所有的u都不会影响最短路径生成树，由乘法原理即可得到，这是无后效性的，因为最终n个节点必定会连通 #define x first #define y second #define mp make_pair #define int long long #define p ((1ll<<31)-1) priority_queue pair int head[10005],nxt[1000005],ver[1000005],cost[1000005],d[1000005],vis[1000005],tot,n,m,cnt[100050]; void add(int u,int v,int w){ nxt[++tot]=head[u],ver[tot]=v,cost[tot]=w,head[u]=tot; } void dijkstra(){ q.push(mp(0,1)); memset(d,0x3f,sizeof d); d[1]=0; while(q.size()){ int u=q.top().y,w=d[u];q.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=nxt[i]){ int v=ver[i],z=cost[i]; if(d[v]>w+z){ d[v]=w+z; q.push(mp(-d[v],v)); } } } //for(int i=1;i<=n;i++)printf("%d ",d[i]); //puts(""); } int prim(){ for(int u=1;u<=n;u++){ for(int i=head[u];i;i=nxt[i]){ int v=ver[i]; if(d[u]+cost[i]==d[v])cnt[v]++; } } int ans=1; for(int i=1;i<=n;i++)if(cnt[i])ans=ans*cnt[i]%p; return ans; } signed main(){ // freopen("castle8.in","r",stdin); scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } dijkstra(); printf("%lld\n",prim()); } 这道题是关于最短路径生成树模型的，并且求方案数，结论务必理解记忆 例题4野餐规划 一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。 现在他们想要去公园玩耍，但是他们的经费非常紧缺。 他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。 为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。 由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。 公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。 现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。 第一行包含整数 n，表示人和人之间或人和公园之间的道路的总数量。 接下来 n 行，每行包含两个字符串 A、B 和一个整数 L，用以描述人 A 和人 B 之前存在道路，路长为 L，或者描述某人和公园之间存在道路，路长为 L。 道路都是双向的，并且人数不超过 20，表示人的名字的字符串长度不超过 10，公园用 Park 表示。 再接下来一行，包含整数 s，表示公园的最大停车数量。 你可以假设每个人的家都有一条通往公园的道路。 简述题意，其实就是说，求图上的一颗生成树，使得1号节点的入度不超过S的情况下权值和最小 这里介绍一种并不常用的最小生成树算法：消圈算法 简单来说，就是在无向图上随便指定一颗生成树，然后考虑剩下的边，加入一个就会产生环，然后把环上最大的边断开，这样重复操作直到加入的边比环上最大边还要大为止，这样就得到了最小生成树，只不过由于程序实现比较复杂，复杂度也并不突出，于是就很少用（最古老的最小生成树算法） 对于本题，我们需要使用这种思想 首先，我们将1号节点与其他节点的边断开，这样我们就得到了若干个连通块，对每一个连通块分别求最小生成树，设有T个连通块,若T>S本题无解，因为不可能连通 然后我们尝试对于一个连通块T_i，T_i中所有与1有边的节点，我们选择最小的那一个进行连接，这样我们就连通了这个连通块，以此类推，我们就得到了原图的一棵生成树 接着我们就使用消圈算法的思想，尝试改动S-T条边使得答案更优，由于每个连通块内部再无需改动了，因为连通块内部求了最小生成树，于是我们的改动也只与1号节点有关 我们考虑与1号节点有边但边没有选入生成树的节点，将其加入生成树后势必会形成一个环，在环上找最大的边(假设这个点是x,则我们需要找到的最大的边就是原生成树上1->x的最大边)进行断开，就得到了一个权值和更小的生成树，重复这个步骤直到改动完S-T条边或者改动的边无法加入生成树为止，这个步骤需要我们维护1号节点在生成树上到每个节点所经过的边的边权最大值，可以使用深度优先遍历维护 int cnt,m,s,deg,ans,a[32][32],d[32],lst[32],vis[32],c[32],t[32][32],ver[32],p,f[32],mxx[32],mxy[32]; //t数组维护目前的最小生成树森林，f、mxx、mxy维护的是1->x的路径上的最大边 map void prim(int rt){//求连通块内部最小生成树，使用prim更好处理 d[rt]=0; for(int i=1;i<=p;i++){ int u=0; for(int j=1;j<=p;j++) if(!vis[ver[j]] &&(u==0||d[ver[j]] vis[u]=1; for(int j=1;j<=p;j++){ int v=ver[j]; if(!vis[v]&&d[v]>a[u][v]) d[v]=a[u][v],lst[v]=u; } } int maxx=rt; for(int i=1;i<=p;i++){ int u=ver[i]; if(rt==u)continue; ans+=d[u]; t[lst[u]][u]=t[u][lst[u]]=d[u]; if(a[1][u] } deg++; ans += a[1][maxx]; t[1][maxx]=t[maxx][1]=a[1][maxx]; } void dfs(int u){//划分连通块 ver[++p]=u; c[u]=1; for(int v=1;v<=cnt;v++) if(a[u][v] != 0x3f3f3f3f && !c[v])dfs(v); } void Prim(){//求各个连通块内的最小生成树 memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); memset(t,0x3f,sizeof(t)); c[1]=1; for(int i=2;i<=cnt;i++) if(!c[i]){ p=0; dfs(i); prim(i); } } void dp(int u){//计算f、mxx、mxy， vis[u]=1; for(int v=2;v<=cnt;v++) if(t[u][v] != 0x3f3f3f3f && !vis[v]){ if(f[u]>t[u][v]) f[v]=f[u],mxx[v]=mxx[u],mxy[v]=mxy[u]; else f[v]=t[u][v],mxx[v]=u,mxy[v]=v; dp(v); } vis[u]=0; } bool solve(){//执行最后的消圈过程 int mn=1<<30,id; for(int i=2;i<=cnt;i++){ if(t[1][i]!=0x3f3f3f3f||a[1][i]==0x3f3f3f3f)continue; if(a[1][i]-t[mxx[i]][mxy[i]] mn=a[1][i]-t[mxx[i]][mxy[i]]; id=i; } } if(mn>=0)return 0; ans+=mn,t[1][id]=t[id][1]=a[1][id]; t[mxx[id]][mxy[id]]=t[mxy[id]][mxx[id]]=0x3f3f3f3f; f[id]=a[1][id],mxx[id]=1,mxy[id]=id; vis[1]=1; dp(id); return 1; } int main(){ H["Park"]=1;cnt=1;//注意P是大写的(调试2h就因为这个) scanf("%d",&m); memset(a,0x3f,sizeof(a)); for(int i=1;i<=m;i++){ int u,v,w; char x[15],y[15]; scanf("%s%s%d",x,y,&w); if(!H[x])H[x]=++cnt; if(!H[y])H[y]=++cnt; u=H[x],v=H[y]; a[u][v]=a[v][u]=min(a[u][v], w); } scanf("%d",&s); Prim(); memset(vis,0,sizeof(vis)); dp(1); while(deg if(!solve())break; deg++; } printf("Total miles driven: %d\n",ans); } 此题启发我们消圈思想，拆图计算，合并消圈 例题5:四叶草魔杖 题目描述 给定一张无向图，结点和边均有权值。所有结点权值之和为 0，点权可以沿边传递，传递点权的代价为边的权值。求让所有结点权值化为 0 的最小代价。 解法 容易想到本题与最小生成树有关。一种不难想出的思路是求出原图的最小生成树，将最小生成树上所有边的权值之和作为答案。 但经过思考，可以发现这样得到的不一定是最优解。首先，原图可能并不联通；其次，可以将原图划分为若干个点权之和均为 0 的子图，在这些子图中分别转移点权，最后将答案合并。这样得到的方案或许会更优。 此时我们发现划分方案不止一种，如何确定最终的方案成了需要解决的最大问题。 注意到本题中 \(N\) 范围较小，允许我们把所有点权和为 0 的子图（以下简称“合法子图”）的最小生成树全部求出。因此可以先枚举原图点集的所有子集，对于每个点权和为 0 的点集，用这些点和连接它们的边构造一张合法子图。我们能够轻易求出这些合法子图的最小生成树。但有些合法子图或许并不联通，为避免对之后的求解造成影响，需要把这些子图的最小生成树边权和设为 \(∞\). 接下来需要把这些子图中的若干个合并起来，得到全局最优解。与划分的情形相同，合并这些子图的方案也有多种。可以使用 \(DP\) 得到最优解。 具体地，考虑进行类似背包的 \(DP\)，将每个合法子图视作可以放入背包的一个物品。设 \(A、B\)为两个不同合法子图的点集，合法子图的最小生成树边权和为 \(S\)，可以写出如下状态转移方程： \(f_{A∪B}=\min\lbrace f_{A∪B},f_A+S_B\rbrace,A∩B=⊘\) 最终 \(f_{2^n-1}\) 即为所求的答案。至此，本题得到解决。 int n,m,a[20],fa[20],s[1<<16],f[1<<16],ans[1<<16]; struct node{ int u,v,w; bool operator <(const node b)const{ return w } }t[150]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} int kruskal(int S){ int ans=0; for(int i=0;i if(S&(1< for(int i=1;i<=m;i++){ if(!(S&(1< int u=find(t[i].u),v=find(t[i].v); if(u!=v){ fa[u]=v; ans+=t[i].w; } } int op=-1; for(int i=0;i if(S&(1< if(op==-1)op=find(i); else if(find(i)!=op)return 0x3f3f3f3f; return ans; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i scanf("%d",&a[i]); for(int i=1;i<(1< for(int j=0;j if(i&(1< if(!m){ if(s[(1< else puts("0"); return 0; } for(int i=1;i<=m;i++) scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].w); sort(t+1,t+m+1); for(int i=1;i<(1< if(s[i]==0)ans[i]=kruskal(i); f[i]=0x3f3f3f3f; } f[0]=0; for(int i=1;i<(1< if(s[i])continue; for(int j=0;j<(1< if(!(i&j)) f[i|j]=min(f[i|j],f[j]+ans[i]); } if(f[(1< else printf("%d",f[(1< } 这题是一道动态规划与最小生成树的综合题，主要启发我们缜密思考题目，学会把题目转化为图论模型 总的来说，今天这一节需要掌握的知识点有 最小生成树的kruskal和prim算法，消圈算法思想 最小生成树定理及推论 最优比率生成树，结合0/1分数规划模型 最短路径生成树的定义与性质 需要掌握的思想有 拆分图形，分而治之 单调性思想 DP结合图论