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

· · 题解

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

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

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

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

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

则

m=s-1+\sum\limits_{i=1}^{s}f(G) $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;
}