BZOJ2935: [Poi1999]原始生物【欧拉回路】

2935: [Poi1999]原始生物

【题目描述】

传送门

【题解】

先考虑每个连通块,必须要变成欧拉回路,但是可以删去一条边,所以对于每个连通块所需要的是度数绝对值和/2-1。对于不同的连通块,至少需要一条边与之相连。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int n,fa[MAXN],D[MAXN],Ans,MAX;bool vis[MAXN],flg[MAXN];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);Ans=n;
    for(int i=1;i<=1000;i++) fa[i]=i;
    for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),D[x]++,D[y]--,fa[get(x)]=get(y),vis[x]=vis[y]=1,MAX=max(MAX,max(x,y));
    for(int i=1;i<=MAX;i++) if(D[i]>0) flg[get(i)]=1,Ans+=D[i];
    for(int i=1;i<=MAX;i++) if(!flg[i]&&vis[i]&&get(i)==i) Ans++;
    printf("%d\n",Ans);
    return 0;
} 

发表评论

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

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部