题解：P2451 [SDOI2005] 遗传代码

· · 题解

一本通提高篇的题居然还能写题解。

三倍经验：P2451，P5921，SP211。

题目很明显是让我们求：

对于给定的有向图，加多少边能够存在欧拉路径？

首先我们考虑，怎样才能存在欧拉路径？

不会的去这里。

有向图是半欧拉图当且仅当：

对于第一个要求：显然如果在有向图中弱连通，在无向图中就是强联通的。图可能不连通，点可能不连续存在，要用并查集维护。

第二、三个要求：对于每个子图，容易发现因为有向图中边的入度和出度相等，如果一个有向图中只有一个点出度与入度之差为 1，那么必有一个其他节点入度与出度之差为 1。那么很明显，我们每加一条边，都能让所有节点的入度与出度之差的绝对值的和（\sum_{i \text{存在}} |in_i-out_i|）减 2，那么当 \sum_{i \text{存在}} |in_i-out_i|=2 时，就存在欧拉回路了。加边的数量为 \dfrac{\sum_{i \text{存在}} |in_i-out_i|-2}{2}。

第四个要求：在满足第二、三个要求时此要求必满足。

那么再把每个子图连起来，只需要把上个子图的终点到下个子图的起点连起来，答案为子图的数量 -1。

答案即为：

子图个数-1+\sum_{\text{子图存在}}\max(0,\dfrac{\sum_{i \text{存在}} |in_i-out_i|-2}{2})

又因为本题还需要有 n+1 长度的初始序列来保证包括所有 (l,r)，所以最终答案即为：

n+子图个数+\sum_{\text{子图存在}}\max(0,\dfrac{\sum_{i \text{存在}} |in_i-out_i|-2}{2})

代码：

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=1e3+1;
int n,u,v,d[N],fa[N],cun[N],s[N],cnt;
int find(int x){
    return x==fa[x]? x:fa[x]=find(fa[x]);
}
int main(){
    for(int i=0;i<N;i++) fa[i]=i;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>u>>v;
        d[u]++;
        d[v]--;
        cun[u]=1,cun[v]=1;
        u=find(u),v=find(v);
        fa[v]=u;
    }
    for(int i=0;i<N;i++){
        if(cun[i]) s[find(i)]+=abs(d[i]);
    }
    for(int i=0;i<N;i++){
        if(cun[i]&&find(i)==i) cnt+=max(0,(s[i]-2)/2)+1;
    }
    cout<<n+cnt;
}