原始生物的遗传密码 解题报告
问题描述
原始生物的遗传密码是一个自然数的序列K=(a1,…,an)。原始生物的特征是指在遗传密码中连续出现的数对（l,r），即存在自然数i使得l=ai且r=ai+1。在原始生物的遗传密码中不存在(p，p)形式的特征。
求解任务： 请设计一个程序：
•从文件PIE.IN中读入一系列的特征。
•计算包含这些特征的最短的遗传密码。
•将结果写到文件PIE.OUT中。
输入： 在输入文件PIE.IN的第一行是一个整数n ，表示特征的总数。在接下来的n行里，每行都是一对由空格分隔的自然数l 和r ，1 <= l，r <= 1000。数对（l， r）是原始生物的特征之一。
输入文件中的特征不会有重复。
输出： 输出文件PIE.OUT的唯一一行应该包含一个整数，等于包含了PIE.IN中所有特征的遗传密码的最小长度。
样例输入： 12 2 3 3 9 9 6 8 5 5 7 7 6 4 5 5 1 1 4 4 2 2 8 8 6
样例输出： 15
注： PIE.IN中的所有特征都包含在以下遗传密码中： (8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)
解题思路
本人刚开始做这道题目的时候，认为这个题应该采用的方法是求连通分量。实际上后来才知道，从本质上来说就是利用欧拉回路解决问题。
把每个特征串看作图中的一条边，建立一个图。假设边数为N，如果这个图正好有一个欧拉回路（欧拉回路要求遍历所有的边，然后回到起点。），那么显然所需要的边数为N+1。如果这个图中不存在欧拉回路，那么我们只需计算，至少需要增加的边数k，能使图中存在一个欧拉回路。则N+k就是结果。
一个有向图存在欧拉回路的充要条件是图中有且只有一个连通分量且每一点的出度等于入度。假设图中只存在一个连通分量，则至少增加的边数k＝每个点出度入度之差的绝对值之和的二分之一。
如果图中存在多个连通分量，则对于每个连通分量，按一个连通分支的方法求其至少的加边数，再加上本来就存在欧拉回路的连通分量的个数，就是k的值。
求连通分量，可以用广搜或者并查集(我使用了并查集)，时间复杂度为O(N)。
完整代码
//By Ceeji
//HAOI Test 3 - Problem 2 : Pie
//Date: 2009-4-5
//Type: Graph
//States: Accepted
Program pie;
Const maxl=1000;
inf='pie.in';
ouf='pie.out';
Type node=record
i,next:longint;
end;
Var f:array[1..maxl]of longint;
bcj:array[1..maxl]of longint;
d:array[1..maxl,1..2]of longint; //1: Ru Du 2:Chu du
y:array[1..maxl]of boolean;
c:array[1..1000000]of node;
b:array[1..maxl]of boolean;
n,maxn,minn,max,cn,temp,ans,time,i,kk:longint;
k:array[1..maxl]of longint;
dfq:array[1..maxl]of boolean;
Function getFather(p:longint):longint;
begin
if (bcj[p]=0)or(bcj[p]=p) then exit(p);
bcj[p]:=getFather(bcj[p]);
exit(bcj[p]);
end;
Procedure init;
var i,j,k:longint;
begin
readln(n);
fillchar(f,sizeof(f),0);
fillchar(c,sizeof(c),0);
fillchar(y,sizeof(y),0);
fillchar(d,sizeof(d),0);
fillchar(bcj,sizeof(bcj),0);
fillchar(k,sizeof(k),0);
fillchar(dfq,sizeof(dfq),0);
cn:=0;
for i:=1 to n do
begin
readln(j,k);
inc(cn);
c[cn].i:=k;
c[cn].next:=f[j];
f[j]:=cn;
y[j]:=true;
inc(d[j,2]);
inc(d[k,1]);
end;
close(input);
ans:=0; time:=0;
end;
Procedure doit(i:longint);
var k:longint;
begin
k:=f[i];
while k<>0 do
begin
if (getFather(c[k].i)<>getFather(i)) then
begin
bcj[getFather(c[k].i)]:=getFather(i);
doit(c[k].i);
end;
k:=c[k].next;
end;
end;
Procedure print;
var i,j:longint;
begin
j:=0;
for i:=1 to 1000 do
inc(j,k[i]);
writeln(cn+kk+j>>1);
close(output);
end;
begin
assign(input, inf); reset(input);
assign(output,ouf); rewrite(output);
init;
for i:=1 to maxl do
if (y[i]) then
doit(i);
for i:=1 to maxl do
if (y[i]) and (bcj[i]=0) then bcj[i]:=i;
for i:=1 to maxl do
begin
inc(k[getFather(i)],(abs(d[i,1]-d[i,2])));
end;
for i:=1 to 1000 do
begin
if (dfq[getFather(i)]=false)and(y[i]) then
begin
dfq[getFather(i)]:=true;
if k[getFather(i)]=0 then inc(kk);
end;
end;
print;
end.
题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。
© 转载需附带本文链接，依据 CC BY-NC-SA 4.0 发布。