[POI1999][LOJ10112]原始生物

典型的有向图K笔画的问题

最后答案就是n+1-1+k

1笔画有一点入度比出度少1

k笔画则统计入度比出度少的点中所有少的总和

#include<bits/stdc++.h>
using namespace std;
int n,a,b,ans;
int flag[1005],fa[1005],out[1005],in[1005],tot[1005]; 
int read()
{
    int ch=0,x=0;while(ch=getchar(),ch<‘0‘||ch>‘9‘);
    while(x=x*10+ch-48,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
    return x;
}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void conn(int x,int y)
{
    int fxx=getfa(x),fyy=getfa(y);
    if(fxx!=fyy)fa[fxx]=fyy;
}
int main()
{
    n=read();ans=n;
    for(int i=1;i<=1000;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
    a=read(),b=read(),flag[a]=1,flag[b]=1,out[a]++,in[b]++,conn(a,b);
    for(int i=1;i<=1000;i++)
    if(in[i]>out[i])tot[getfa(i)]+=in[i]-out[i];
    for(int i=1;i<=1000;i++)
    if(flag[i])if(getfa(i)==i)if(tot[i]==0)ans++;else ans+=tot[i];
    printf("%d",ans);
    return 0;
}

[POI1999][LOJ10112]原始生物

原文：https://www.cnblogs.com/DavidJing/p/10386935.html