LuoguP2700逐个击破【并查集/生成树/正难则反】By cellur925

题目大意：给你一棵树，求把其中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*];

 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=;i<=k;i++)

     {

         int x=;

         scanf("%d",&x);

         vis[x]=;

     }

     for(int i=;i<=n-;i++)

         scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val),ans+=edge[i].val;

     for(int i=;i<=n;i++) fa[i]=i;

     sort(edge+,edge++n-,cmp);

     for(int i=;i<=n-;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]=;

         else if(vis[qq]) vis[pp]=;

     }

     printf("%lld",ans);

     return ;

 }

巴特西

LuoguP2700逐个击破【并查集/生成树/正难则反】By cellur925

最新文章

热门文章