题解 P2121 【拆地毯】

顾z

2018-09-14 10:56:01

Solution

# [顾z](https://www.cnblogs.com/-guz/) 题目描述--->[p2121 拆地毯](https://www.luogu.org/problemnew/show/P2121) ## 分析 这题**为什么是最大生成树**. ~~先来bb两句~~ 题目为拆地毯,让我们剩下k个地毯. 题目想要我们**求得最大的美丽度**. 且要求我们 ``保留的地毯构成的图中,任意可互相到达的两点间只能有一种方式互相到达`` 很明显,这一要求提示了我们最后结构会是一棵树 (因为树上路径唯一啊,qwq. 然后根据**正难则反**的思想. 我们考虑**拼地毯**. 所以我们就想到了**kruskal算法**.(`・ω・´) 与普通kruskal不同的是,这里是一个**最大生成树** 我们**拼到k个得到的最大美丽度就是答案** **为什么是拼到k个**? 给大家一个图. ![](https://i.loli.net/2018/09/14/5b9b21927734f.png) 如果此时题目要求我们剩下6个地毯,很明显我们将6个地毯放入同一个并查集中就可满足条件. (已经预处理出较大美丽度的情况下) **拆地毯,让我们剩下k个,因此我们合并出k个即可** ~~所以就裸了~~ ## 做法 我们只需要对最小生成树略微修改,把**边权从大到小排序**即可. **注意判断已经加入到同一个并查集中的数量为k.** ------------------代码------------------ ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int using namespace std; IL void in(int &x) { int f=1;x=0;char s=getchar(); while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();} while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } int fa[100008],n,m,ans,cnt,k; struct E{int pre,to,w;}edge[400008]; IL bool cmp(const E&a,const E&b) { return a.w>b.w; }//边权从大到小排序. IL int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }//路径压缩并查集 IL void kruskal() { sort(edge+1,edge+m+1,cmp);//排序 for(RI i=1;i<=m;i++) { RI u=edge[i].pre,v=edge[i].to,w=edge[i].w; int fu=find(u),fv=find(v); if(fu==fv) continue; ans+=w;fa[fv]=fu; cnt++; if(cnt==k) break;//判断已经拼了k个地毯. } } int main(){ in(n),in(m);in(k); for(RI i=1;i<=n;i++) fa[i]=i;//并查集初始化. for(RI i=1;i<=m;i++) in(edge[i].pre),in(edge[i].to),in(edge[i].w); kruskal();//kruskal操作 printf("%d",ans); } ```