洛谷P5921 [POI1999] 原始生物题解

题目链接：P5921 [POI1999] 原始生物

题意：

原始生物的遗传密码是一个自然数的序列 $K=(a_1,…,a_n)$。

原始生物的特征是指在遗传密码中连续出现的数对 $(l,r)$，即存在自然数 $i$ 使得 $l=a_i$ 且 $r=a_{i+1}$。

在原始生物的遗传密码中不存在 $(p,p)$ 形式的特征。

请设计一个程序：

读入一系列的特征。

计算包含这些特征的最短的遗传密码。

将结果输出.

输入格式：

第一行是一个整数 $n$ ，表示特征的总数。

在接下来的 $n$ 行里，每行都是一对由空格分隔的自然数 $l$ 和 $r$。

数对 $(l,r)$ 是原始生物的特征之一。

输入文件中的特征可能会有重复，请过滤掉。

输出格式：

唯一一行应该包含一个整数，为包含了所有特征的遗传密码的最小长度。

数据范围：

$1\le n\le 10^6,~1\le l,r\le1000$ 。

题目要求一个序列，使得每条边都在序列中出现过。

考虑将现在图中所有的弱连通分量分为两种类型：存在欧拉回路的和不存在欧拉回路的。

设 $m_i$ 为当前弱连通分量的边数

存在欧拉回路的（此时实际上强连通），贡献为 $m_i+1$ ，此时
$\sum_i \left|\mathrm{deg}_{\rm in}(i) - \mathrm{deg}_{\rm out}(i)\right| = 0$
不存在欧拉回路的，此时
$\sum_i \left|\mathrm{deg}_{\rm in}(i) - \mathrm{deg}_{\rm out}(i)\right| = 2k\quad(k>0)$
贡献为 $m_i+k$ 。因为我们可以，且每添加一条正确的边，就会让差值减去 $2$ ，直到变成 $0$ 。

因为弱连通分量只要把边替换成无向边就是连通块了，所以我们可以用并查集维护每个弱连通分量的度数差值。

时间复杂度 $\mathcal{O}(n\alpha(n) + m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))
#define M ((int)(1e6 + 15))

char used[N][N], vis[M];
int n, res, in[N], out[N], U[M], V[M], f[N], sum[N], sz[N]; 
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int u, int v)
{
    int x = find(u), y = find(v);
    if(sz[x] > sz[y]) swap(x, y);
    if(x == y) return; 
    else { f[x] = y, sz[y] += sz[x], sum[y] += sum[x]; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> m; res = m;
    for(int i = 1; i <= m; i++)
    {
        int &u = U[i], &v = V[i];
        cin >> u >> v; if(used[u][v]) { --res; U[i] = V[i] = -1; continue; }
        used[u][v] = true; up(n, max(u, v)); 
        ++out[u]; ++in[v]; vis[u] = vis[v] = true;
    }
    for(int i = 1; i <= n; i++) { 
        f[i] = i, sz[i] = 1, sum[i] = (abs(in[i] - out[i]));
    }
    for(int i = 1; i <= m; i++) {
        int &u = U[i], &v = V[i]; if(u != -1) merge(u, v);
    }
    for(int i = 1; i <= n; i++)
        if(vis[i] && find(i) == i) res += 1 + max(0ll, (sum[i] - 2) / 2);
    cout << res << '\n';
    return 0;
}