首页 > 其他分享 >HDU 4313 Matrix (贪心)

HDU 4313 Matrix (贪心)

时间:2023-04-13 22:36:21浏览次数:54  
标签:bin HDU 4313 const Matrix int ha MAXN include


题目地址:HDU 4313
利用最小生成树的思想,这里是从大往下删,能删则删,不能删就留着。用个并查集维护下。代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <string>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
int ha[MAXN], bin[MAXN];
struct node
{
        int u, v, w;
        bool operator < (const node &tmp) const{
                return w>tmp.w;
        }
}fei[MAXN];
int find1(int x)
{
        return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void init(int n)
{
        memset(ha,0,sizeof(ha));
        for(int i=1;i<=n;i++){
                bin[i]=i;
        }
}
int main()
{
        int t, n, k, u, v, f1, f2, i;
        LL ans;
        scanf("%d",&t);
        while(t--){
                scanf("%d%d",&n,&k);
                init(n);
                ans=0;
                for(i=0;i<n-1;i++){
                        scanf("%d%d%d",&fei[i].u,&fei[i].v,&fei[i].w);
                        ans+=(LL)fei[i].w;
                }
                for(i=0;i<k;i++){
                        scanf("%d",&u);
                        ha[u]=1;
                }
                sort(fei,fei+n-1);
                for(i=0;i<n-1;i++){
                        f1=find1(bin[fei[i].u]);
                        f2=find1(bin[fei[i].v]);
                        if(!ha[f1]||!ha[f2]){
                                ans-=(LL)fei[i].w;
                        }
                        bin[f2]=f1;
                        ha[f1]+=ha[f2];
                }
                printf("%I64d\n",ans);
        }
        return 0;
}


标签:bin,HDU,4313,const,Matrix,int,ha,MAXN,include
From: https://blog.51cto.com/u_16070138/6188455

相关文章

  • HDU 4628 Pieces (状压DP)
    题目地址:HDU4628这题没想到怎么快速枚举子状态。。。看了题解才知道的。用for(state=i;state>0;state=(state-1)&i)就可以了。这题的具体做法是先预处理出所有的状态是不是回文串,然后就是普通的DP了。代码如下:#include<iostream>#include<string.h>#include<math.h>......
  • HDU 4812 D Tree (树上点分治)
    题目地址:HDU4812这题是13年南京区域赛的现场题。树分治思想。树分治的过程中记录下每个子树的所有到达根的路径的积,用best记录下每个积的最小端点,然后再枚举当前子树的每个积,然后用逆元的方法求出当积为k时所需要的另一个端点值,并更新答案。代码如下:#include<iostream>#......
  • HDU 5145 NPY and girls (莫队分块离线)
    题目地址:HDU5145莫队真的好神奇。。这样的复杂度居然只有n*sqrt(n)。。。裸的莫队分块,先离线,然后按左端点分块,按块数作为第一关键字排序,然后按r值作为第二关键字进行排序。都是从小到大,可以证明这样的复杂度只有n*sqrt(n)。然后进行块之间的转移。代码如下:#include<ios......
  • HDU 5016 Mart Master II (树上点分治)
    题目地址:HDU5016先两遍DFS预处理出每个点距最近的基站的距离与基站的编号。然后找重心,求出每个点距重心的距离,然后根据dis[x]+dis[y]<d[y],用二分找出当前子树中不会被占领的数量,总点数减去即是被占领的数量。这样就可以求出每个点最多占领的点的数量。然后找最大值即可。......
  • HDU 1452 Happy 2004 (积性函数)
    题目地址:HDU1452性质1:如果gcd(a,b)=1则S(a*b)=S(a)*S(b)2004^X=4^X*3^X*167^XS(2004^X)=S(2^(2X))*S(3^X)*S(167^X)性质2:如果p是素数则S(p^X)=1+p+p^2+…+p^X=(p^(X+1)-1)/(p-1)因此:S(2004^X)=(2^(2X+1)-1)*(3^(X+1)-1)/2*(167^(X+1)-1)/166......
  • HDU 4864Task(多校联合训练1)(贪心)
    题目地址:HDU4864这题又是一上来认为是最小费用流,但是边太多,果然,敲完交上去后不断TLE。。小优化了两次也没过。。。sad。。后来看了题解才发现是贪心。。。贪心也不好想。大体思路是很好想的,就是先都按时间从大到小排序,再遍历任务,从机器里找能匹配的,并在能匹配的里边找等级尽量小的......
  • HDU 1864最大报销额(一维背包)
    题目地址:HDU1864刚上来看着挺麻烦的。。仔细看了看原来好简单好简单。。。只要去掉一些不符合要求的发票,剩下的就是最简单的背包问题了。。对于小数问题,只要*100就变成整数了。代码如下:#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include......
  • HDU 5045 Contest(费用流)
    题目地址:HDU5045终于在比赛中用网络流A了一道题。。。刷了那么多网络流,终于用到一次了。。虽然题目很简单,但是还是要纪念一下下。。。我这题的思路就是求m/n次费用流,每n个算作同一轮,对这同一轮的求最大费用流。建图就很简单了,最简单的二分图模型。代码如下:#include<iostre......
  • HDU 1856 More is better(并查集+离散化)
    题目地址:HDU1856水题。由于标号范围太大,而数据数只有10w,所以要先进行离散化。然后就是裸的并查集了。代码如下:#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<stdlib.h>#include<math.h>#include<ctype.h>#include<que......
  • HDU 2473 Junk-Mail Filter(并查集的删除操作)
    题目地址:HDU2473这题以前碰到过,没做出来。。现在又做了做,还是没做出来。。、、这题涉及到并查集的删除操作。想到了设一个虚节点,但是我把虚节点设为了要删除的点的父节点,一直是栈溢出,目测是无限递归了。看了看别人的做法,原来只要建一个映射就可以了,虚节点是作为的新的映射,每......