最大生成树|最大权森林

淡淡的烟草味﹌ 2021-10-18 12:44 272阅读 0赞

http://poj.org/problem?id=3723

题意：给定n个男生和m个女生的关系，各个关系具有一定的权值，然后要挑选出所有人，每个人的代价是10000，但挑选人的过程中这些权值就是可以用来减去费用，求cost的min

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int M=5e4+5;
    const int N=1e4+4;
    
    struct node{
        int  u,v,w;
    }e[M];
    int fa[N<<1];
    bool cmp(node p,node q){
        return p.w>q.w;
    }
    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }
    
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            int n,m,k;
            scanf("%d%d%d",&n,&m,&k);
            for(int i=0;i<k;i++){
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                v+=n;
                e[i].u=u;
                e[i].v=v;
                e[i].w=w;
            }
            for(int i=0;i<2*n;i++)
                fa[i]=i;
            sort(e,e+k,cmp);
            int ans=0,countt=0;
            for(int i=0;i<k;i++){
                int u=e[i].u,v=e[i].v;
                int a=find(u),b=find(v);
                if(a!=b){
                    fa[a]=b;
                    ans+=e[i].w;
                }
            }
            printf("%d\n",(n+m)*10000-ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/starve/p/11304129.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/68079a80bf3d402dbb03919dd67917c3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，272人围观）

还没有评论，来说两句吧...

相关阅读

相关最小权点覆盖集与最大权独立集

最小权点覆盖集一、定义什么是点覆盖集呢？就是图中所有点的一个子集，首先他是一个点集，然后图中所有边的两个端点的其中一个都在这个点集中，就是说这个点集中包含了所有

ゞ浴缸里的玫瑰/ 2022年11月03日 05:49/ 0 赞/ 226 阅读

相关最大权闭合子图

闭合图首先，先了解什么是闭合图。闭合图一般指一个图中点的集合，从该集合中所有的点出发，能到达的点要求都必须在该点集中。也就是说，从该集合中出发，一定要回到该集合中，不能

￡神魔★判官ぃ/ 2022年10月29日 12:29/ 0 赞/ 134 阅读

相关求树的最大宽度和最大深度

原文地址：http://blog.csdn.net/salahelx/article/details/46727499 二叉树深度：这个可以使用递归，分别求出左子树的深度、右

以你之姓@/ 2022年09月26日 02:22/ 0 赞/ 178 阅读

相关最大权闭合子图（模板）

参考博客： http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html http://www.cnbl

- 日理万妓/ 2022年09月25日 11:26/ 0 赞/ 120 阅读

相关 poj 3723 Conscription 【最大生成树|最大权森林】

题目：[poj 3723 Conscription][] 题意：要征兵n个男兵和m个女兵，每个花费10000元，但是如果已经征募的男士兵中有和将要征募的女士兵关系好

ゝ一世哀愁。/ 2022年08月06日 00:21/ 0 赞/ 158 阅读

相关 HDU 6187 Destroy Walls（最大生成树）

Long times ago, there are beautiful historic walls in the city. These walls divide the c

蔚落/ 2022年06月09日 12:19/ 0 赞/ 128 阅读

相关最大堆的生成

include <deque> include <iostream> include <cmath> include <fstream>

快来打我*/ 2022年04月24日 03:46/ 0 赞/ 165 阅读

相关最大权闭合子图

闭合图：对于一个有向图G，存在点集合V，任取点u属于V，u的出边的另一个点也属于V，则为闭合图。最大权闭合子图：当每个点有一个权值w（有正有负），点权和最大的闭合图为

怼烎@/ 2022年01月10日 13:07/ 0 赞/ 203 阅读

相关 POJ 3723 Conscription——————求森林最大权

[Conscription][] Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 19544 A

╰+哭是因爲堅強的太久メ/ 2021年12月03日 04:29/ 0 赞/ 273 阅读

相关最大生成树|最大权森林

http://poj.org/problem?id=3723 题意：给定n个男生和m个女生的关系，各个关系具有一定的权值，然后要挑选出所有人，每个人的代价是10000，但挑选

淡淡的烟草味﹌/ 2021年10月18日 12:44/ 0 赞/ 273 阅读