自动搬运

查看原文

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 21:37:50，当前版本为作者最后更新于2024-09-24 20:58:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

三倍经验：P2451，P5921，SP211。

题目很明显是让我们求：

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

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

不会的去这里。

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

• 非零度顶点是弱连通的。
• 至多一个顶点的出度与入度之差为 $1$。
• 至多一个顶点的入度与出度之差为 $1$。
• 其他顶点的入度和出度相等。

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

第二、三个要求：对于每个子图，容易发现因为有向图中边的入度和出度相等，如果一个有向图中只有一个点出度与入度之差为 $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;
}