原始生物的遺傳密碼 解題報告
問題描述
原始生物的遺傳密碼是一個自然數的序列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.
© 轉載需附帶本文連結，依 CC BY-NC-SA 4.0 釋出。