题目传送门 https://www.luogu.org/problemnew/show/P2700
题目大意: 给你一棵树, 求把其中 k 个点相互隔离 (不连通) 所需要的边权代价.
这题我开始是想要求出把 k 个点联通的最小代价的, 但后来发现还是实现起来比较困难, 题解里貌似也没有这种做法, 于是就鸽了. 但是大体的思考方向还是不直接去想把 k 个点隔离, 而是把问题转化.
花费最小代价删边 ->花费最大代价建边. 而建边的时候如果遇到一条两边都是敌人的边, 我们显然是不需要建的, 所以这其实我们需要维护敌人的网络, 用并查集来维护.
首先我们标记敌人点, 再把边从大到小排序. 枚举所有的边, 如果它两端点都是敌人, 那肯定不连他. 如果两端点有一个是敌人, 也连上, 并在那个无辜的点上打一个标记, 因为之后的点也不能再连他. 于是我们就可以用并查集维护. 最后注意我们之后调用的都是这个集合的代表元, 即 getf.
Code
- #include<cstdio>
- #include<algorithm>
- #define maxn 100090
- using namespace std;
- typedef long long ll;
- int n,k;
- ll ans;
- int vis[maxn],fa[maxn];
- struct node{
- int to,from,val;
- }edge[maxn*2];
- bool cmp(node a,node b)
- {
- return a.val>b.val;
- }
- int getf(int x)
- {
- if(fa[x]==x) return x;
- return getf(fa[x]);
- }
- int main()
- {
- scanf("%d%d",&n,&k);
- for(int i=1;i<=k;i++)
- {
- int x=0;
- scanf("%d",&x);
- vis[x]=1;
- }
- for(int i=1;i<=n-1;i++)
- scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val),ans+=edge[i].val;
- for(int i=1;i<=n;i++) fa[i]=i;
- sort(edge+1,edge+1+n-1,cmp);
- for(int i=1;i<=n-1;i++)
- {
- int pp=getf(edge[i].from),qq=getf(edge[i].to);
- if(vis[pp]&&vis[qq]) continue;
- ans-=edge[i].val;
- if(qq!=pp) fa[qq]=pp;
- if(vis[pp]) vis[qq]=1;
- else if(vis[qq]) vis[pp]=1;
- }
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2795061.html