此题luogu无题解

所以来一篇

用DSU+特判解决问题

 

先求一下森林和每棵树节点数

对于每个节点分别统计对答案贡献

最后特判一下单独的节点,还要+1

日常水这种题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iterator>
#include<queue>
using namespace std;

int fr,to;
int edgenum=0,fatherx[10010]={0},nodev[10010]={0},ansx=0;
int fmr[10010]={0},ctr[10010]={0};

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline int findx(int e)
{
    if (fatherx[e]!=e) fatherx[e]=findx(fatherx[e]);
    return fatherx[e];
}

int main()
{
    for (int i=1;i<=1001;i++)
    {
        fatherx[i]=i;
        nodev[i]=1;
    }
    readx(edgenum);
    for (int i=1;i<=edgenum;i++)
    {
        readx(fr); readx(to);
        fmr[fr]--; fmr[to]++;
        if (findx(fr)!=findx(to))
        {
            nodev[findx(to)]+=nodev[findx(fr)]; nodev[findx(fr)]=0;
            fatherx[findx(fr)]=findx(to);
        }
    }
    for (int i=1;i<=1001;i++) if (fmr[i]>0) ctr[findx(i)]+=fmr[i]; 
    for (int i=1;i<=1001;i++) if (nodev[i])
    {
        ansx+=ctr[i];
        if (nodev[i]>1 && (!ctr[i])) ansx++;
    }
    
    printf("%d\n",ansx+edgenum);
    return 0;
}

 

分类: DisjointSet(并查集)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.