原始生物

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 681 字

有向欧拉迹补边计数

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1534
// 题意：给定 n 个有序特征对 (l,r)（表示遗传密码中连续出现的 l 后紧跟 r），求包含全部特征的遗传密码的最短长度。
// 思路：把每个数看作点、每个特征 (l,r) 看作有向边 l→r。问题等价于用最少重复边补全成一条欧拉通路，覆盖所有原边。设 S 为出度大于入度的点数（与亏点相等），最短序列长度 = 边数 + max(1,S)。
// 复杂度：O(n) 时间 / O(V) 空间
// 易错点：l,r 范围 1..1000；一个点在序列里可被多次使用；当且仅当图弱连通且出/入度平衡到至多一个源一个汇时存在欧拉通路。
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1005;
int outd[MAXV], ind[MAXV];
int main(){
    int n;
    if(!(cin>>n)) return 0;
    for(int i=0;i<n;i++){
        int l, r;
        cin>>l>>r;
        outd[l]++; ind[r]++;
    }
    int S=0;
    for(int i=1;i<MAXV;i++) if(outd[i]>ind[i]) S++;
    int ans = n + (S==0?1:S);
    cout<<ans<<"\n";
    return 0;
}

原始生物

正文

一本通·提高篇的其它内容