自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:15:39，当前版本为作者最后更新于2020-02-01 17:57:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题面转化：给定一张图，设添加最少 $m$ 条边 可以使得整张图存在欧拉路径。 请输出 $m+n+1$。

欧拉路径是指经过图中每一条边的路径。

---

如果两个图，它们之间没有任何公共边，我们就把它们分成两个子图。

于是我们把给定的图分成 $s$ 个子图，$G_1,G_2,...,G_s$，并且他们的交是原图。

定义 $f(G)$ 表示使图 $G$ 存在欧拉路径，至少需要添加的边数量。

则

$$m=s-1+\sum\limits_{i=1}^{s}f(G)$$

$s$ 求解直接并查集完事

$f(G)$ 怎么求？

根据我们的要求，如果把有向边看成无向边，那么 $G$ 必然是极大联通分量。

设点 $i$ 的入度是 $in_i$ ，出度是 $out_i$。

那么 $\sum\limits_{u\in G} in_u= \sum\limits_{u\in G} out_u$ 是显然的结论。

当每个点的 $in_i=out_i$时，即 $\sum\limits_{u\in G} |in_u-out_u| = 0$ 时 $G$ 有欧拉回路（特殊的欧拉路径）。

当 $\sum\limits_{u\in G} |in_u-out_u| = 2$ 时，存在欧拉路径。

当 $\sum\limits_{u\in G} |in_u-out_u| = 4$ 时，我们只要选择两个点 $u,v(in_u>out_u,in_v<out_v)$

连接一条 $(u,v)$ 的有向边，就会必然导致 $\sum\limits_{u\in G} |in_u-out_u| = 2$

也就是每次总能找到两个点 $u,v$ 导致右侧 $-2$。

而一旦让右边 $\le 2$ 就存在了欧拉路径。

所以得到

$$f(G)=\max\{0,\dfrac{\sum\limits_{u\in G} |in_u-out_u|-2}{2}\} $$

最后温馨提醒这题 n 数据范围是假的

#include <cstring>
#include <iostream>
#include <set>
using namespace std;

#define rg register
#define il inline
#define MX (1000 + 44)

int d[MX] ,fa[MX] ,size[MX] ,occ[MX] ,s[MX];
void init(){
	for(int i = 0 ; i < MX ; ++i)
		fa[i] = i ,size[i] = 1;
}
int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
void link(int u ,int v){
	u = find(u) ,v = find(v);
	if(u == v)	return;
	if(size[u] < size[v])	swap(u ,v);
	fa[v] = u ,size[u] += size[v];
}

struct edge{
	int u ,v;
	bool operator <(const edge& b)const{
		return u == b.u ? v < b.v : u < b.u;
	}
};

set<edge> e;

int main(){
	init();
	int n ,del = 0; cin >> n;
	for(int i = 1 ,u ,v ; i <= n ; ++i){
		cin >> u >> v;
		if(e.find((edge){u ,v}) != e.end()){
			++del;
			continue;
		}
		e.insert((edge){u ,v});
		d[u]++ ,d[v]--;
		occ[u] |= occ[v] |= 1;
		link(u ,v); 
	}
	for(int i = 1 ; i < MX ; ++i)
		if(occ[i])	s[find(i)] += abs(d[i]);
	int cnt = 0;
	for(int i = 1 ; i < MX ; ++i){
		if(occ[i] && find(i) == i){
			cnt += max(0 ,(s[i] - 2) / 2);
			cnt++;
		}
	}
	cout << n + 1 + cnt - 1 - del << endl;
	return 0;
}