Problem

原始生物的遗传密码是一个自然数的序列 K =(a1,...,an)。原始生物的特征是指在遗传密码中连续出现的数对（l,r），即存在自然数 i 使得 l =ai 且 r =ai+1。在原始生物的遗传密码中不存在 (p，p) 形式的特征。
求解任务：
请设计一个程序：

• 读入一系列的特征。
• 计算包含这些特征的最短的遗传密码。
• 将结果输出

Solution

LSYOJ 数据真的水...

首先得各个连通块分别处理。
然后将每个特征看做一个边，则序列长度只跟边数有关。
这题就转化成了加最少的边使每个连通块成一个欧拉路径。

考虑欧拉路径只与度数有关，所以我们只要把出度小的连向入度小的就行了。
这样子一定会形成一个欧拉路径。因为对于一个连通块所有出度不等于入度，入之和 = 出之和。

这样子的贪心对于不连通的两个块是错误的（可能会把其中一个不连通块整成欧拉回路），但分开处理一定不会更坏。因为一定是在第一个块的终点向第二个块的起点连一条边，这样子保证最多对于两个不连通的块至多需要一条边联系起来。

Code

// Code by ajcxsu
// Problem: original life

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int out[N], in[N], p;
int sa[N], sb[N], ta, tb;
int fa[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
void Union(int a, int b) { int af=Find(a), bf=Find(b); if(af!=bf) fa[af]=bf; }
inline void ins(int a, int b) { out[a]++, in[b]++, p++; Union(a, b); }
char vis[N];

int main() {
    ios::sync_with_stdio(false);
    int n, u, v;
    cin>>n;
    for(int i=0;i<n;i++) cin>>u>>v, ins(u, v);
    for(int i=0;i<N;i++)
        if(!fa[i] && (out[i]||in[i])) {
            for(int j=0;j<N;j++)
                if(Find(j)==i) {
                    if(out[j]<in[j]) sa[++ta]=j;
                    else if(out[j]>in[j]) sb[++tb]=j;
                }
            while((ta>1 || in[sa[ta]]-out[sa[ta]]>1) && (tb>1 || out[sb[tb]]-in[sb[tb]]>1)) {
                ins(sa[ta], sb[tb]);
                if(out[sa[ta]]==in[sa[ta]]) ta--;
                if(out[sb[tb]]==in[sb[tb]]) tb--;
            }
            ta--, tb--;
        }
    for(int i=0;i<N;i++)
        if((out[i] || in[i]) && !fa[i]) p++;
    cout<<p<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-2935.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆