Luogu P2700 逐个击破

qwq

同关押罪犯

对于这种希望几个对象分开的题目，只要把并查集反过来想就可以了。

既然要求删除的边权最小，那么只要反过来求给定的点不连通时保留的边权最大即为正解。

同样的，首先将边权排序，不会使敌人连通则连接。

注意事项：1.初始化　　2.最后的答案要定义为long long

bin哥今天讲的：

当加入一条边时，它连接的点只有两种情况：

1.都被占领，这时不能连接；

2.其中一个被占领，需要把另一个也标记为已占领（其实只要把父节点标记就可以了，所以只有（子 & ！父）的情况下需要修改）；

3.都未被占领，连接也无影响，不需要操作。

所以我原来写的：

if(col[xx] && col[yy] && (col[xx]!=col[yy]))continue;

if(col[yy])col[xx] = col[yy];

fa[yy] = xx;

......

就是用染色的方式记录是否连接到敌人。（不知道为什么错了quq）

不过对于这道题，边数为n-1（是一棵树），则一定不会出现环，所以不需要判断连接到的敌人是否是同一个地方，

只要判断有没有占领就行了（占领则一定不同）。

用bool代替int：

 if(col[xx] && col[yy])continue;

 if(col[yy])col[xx] = true;

代码如下

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = ;

int fa[maxn];

bool col[maxn];

int n,k,p;

long long sum;

struct xyw {

    int x,y,w;

}g[maxn];

int getfa(int x){

    if(fa[x] == x)return x;

    else return fa[x] = getfa(fa[x]);

}

bool cmp(xyw i,xyw j){

    return i.w > j.w;

}

int main() {

    scanf("%d%d",&n,&k);

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

        fa[i] = i;

    for(int i = ;i <= k;i++){

        scanf("%d",&p);

        col[p] = true;

    }

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

        scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);

        sum += g[i].w;

    }

    sort(g+,g+n,cmp);

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

        int xx = getfa(g[i].x);

        int yy = getfa(g[i].y);

        if(col[xx] && col[yy])continue;

        if(col[yy])col[xx] = true;

        fa[yy] = xx;

        sum -= g[i].w;

    }

    printf("%lld",sum);

    return ;

}

巴特西

Luogu P2700 逐个击破

最新文章

热门文章