题解 P5921 【[POI1999]原始生物】

破忆 · 2021-11-02 18:57:44 · 题解

【题意】

给定若干条边 (l,r)，要求添加若干条边，构成一条通过所有边的路径，求最小路径长度。

【分析】

记点 i 的入度为 in_i，出度为 out_i。

图构成若干联通块，每个联通块，都要有分成几种情况讨论。

联通块本身有欧拉路径

在这个联通块上不用加边。

存在欧拉回路

等价于对于任意点 i，都有 in_i=out_i。

不存在欧拉回路

等价于存在两个点，|in_i-out_i|=1。

即 \sum |in_i-out_i|=2。

联通块本身无欧拉路径

记 S=\sum |in_i-out_i|。

每加一条边，S 就能减二。

要让 S 减至二，就要加 \frac{S-2}{2} 条边。

综上，联通块内的总代价为 \sum \max(0,\frac{\sum |in_i-out_i|-2}{2})。

还要加上原来的边与连接不同联通块的边。

【算法】

欧拉路径

【代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5,maxm=1e6+5;
int n,m;
int in[maxn],out[maxn];
int d[maxn];
char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int ans;
map<int,bool> hsh;
struct data{
    int x,y;
}a[maxm];
int fa[maxn];
int getfa(int x){
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
    int fx=getfa(x),fy=getfa(y);
    if(fx==fy) return;
    fa[fx]=fy;
    d[fy]+=d[fx];
}
int tot,del;
bool vis[maxn];
int main(){
    freopen("P5921.in","r",stdin);
    freopen("P5921.out","w",stdout);
    m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        if(hsh[x*maxn+y]){del++;continue;}
        hsh[x*maxn+y]=1;
        a[++tot]=(data){x,y};
        in[x]++,out[y]++;
        n=max(n,max(x,y));
        vis[x]=vis[y]=1;
    }
    for(int i=1;i<=n;i++) fa[i]=i,d[i]=abs(in[i]-out[i]);
    for(int i=1;i<=tot;i++) merge(a[i].x,a[i].y);
    for(int i=1;i<=n;i++) if(vis[i]&&getfa(i)==i) ans+=1+max(0,d[i]-2>>1);
    printf("%d\n",m+ans-del);
    return 0;
}