http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=4882

现在在牡丹江，明天regional直播比赛，我会在一个月内退休。求祝福

今天做的热身赛非常紧张称号，总是错的字，晚上写写代码练练手

脑子还是不好使。没想到能够并查集

思路：题目中的操作导致的一个结果是，一条边会成为一个集合的w，----  假设能想到这里可能就能想到并查集吧

WA了由于假设father[x]==x并不能表示x中仅仅有一个数啊。

。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define ll long long#define IN(s) freopen(s,"r",stdin)const int MAXN = 200000+200;struct edge{    int u,v,w;    bool operator < (const edge &c)const{        return w>c.w;    }}e[MAXN*2];int n,fa[MAXN],num[MAXN];ll co[MAXN];int Find(int x){    if(x != fa[x])fa[x]=Find(fa[x]);    return fa[x];}void init(){    for(int i=0;i<=n;i++)        fa[i]=i,num[i]=1,co[i]=0LL;}void un(int x,int y,int w){    int xf=Find(x);    int yf=Find(y);    if(xf == yf)return;    /*if(xf == x && yf == y && num[xf]==1 && num[yf]==1)    {        num[xf]+=num[yf];        fa[yf]=xf;        co[xf]=(ll)w*num[yf]+co[xf];        return;    }*/    ll cosx=(ll)w*num[yf]+co[xf];    ll cosy=(ll)w*num[xf]+co[yf];    if(cosx > cosy)    {        fa[yf]=xf;        num[xf]+=num[yf];        co[xf]=cosx;        //co[y]+=w*num[x];        return;    }    fa[xf]=yf;    num[yf]+=num[xf];    co[yf]=cosy;}ll solve(){    init();    for(int i=1;i
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。