luoguP2700 逐个击破

2023-10-09 14:30

文章标签 击破 luogup2700 逐个

本文主要是介绍luoguP2700 逐个击破，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现自己又做了一道水题

这真的是蓝题吗？

思路和关押罪犯一样

当您A了这道题后，您可以顺利A掉luoguP1525（祝您成功

（不是很明白为什么关押罪犯就是绿题而逐个击破是蓝题

（我觉得关押罪犯更难啊orz

emmmm

正如青青姐所说，这种题要反着想

先将边从大到小排

用color数组标记一下是敌方还是己方（一开始打成了基房orz

如果是敌方就标为true

再从最大的边开始连

如果两个点都是true，显然不行，就跳过，继续下一次循环

如果只有一个点是敌方，就把两个点连到一个并查集里，以便下一次查询

计算最少花费的话，可以先把总花费加起来，每次连一条边，就减去那题条边的边权

或者每次判断不可以连的时候，在结果上加上当前边权

然后。。就没啦

上代码吧～　　

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 100010
#define ll long longint fa[maxn];
bool color[maxn];
ll ans;struct EDGE{int a,b,c;
}edge[maxn];int get(int x){if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}int cmp(EDGE x,EDGE y){return x.c > y.c;
}int main(){int n,k;scanf("%d%d",&n,&k);for(int i = 1;i <= k;i++){int x;scanf("%d",&x);color[x] = true;//标记敌方
  }for(int i = 1;i < n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);edge[i].a = a;edge[i].b = b;edge[i].c = c;ans += c;}for(int i = 1;i <= n;i++)fa[i] = i;sort(edge + 1,edge + n,cmp);for(int i = 1;i < n;i++){int x = get(edge[i].a);int y = get(edge[i].b);if(color[x] && color[y])//敌方不能相连continue;if(color[y])color[x] = true;if(color[x])color[y] = true;fa[x] = y;ans -= edge[i].c;}printf("%lld",ans);//一定要开long long啊！！！return 0;
}

最后还有个问题

我原来开的color是int类型数组

敌方就标记为当前点编号

己方就为零

不知道为什么过不了

【哭唧唧

for(int i = 1;i <= k;i++){int x;scanf("%d",&x);color[x] = x;}

for(int i = 1;i < n;i++){int x = get(edge[i].a);int y = get(edge[i].b);if(color[x] && color[y])continue;if(color[y])color[x] = color[y];if(color[x])color[y] = color[x];fa[x] = y;ans -= edge[i].c;}