本解题报告版权归 Ceeji,转载请保留出处和本注释。
问题描述
原始生物的遗传密码是一个自然数的序列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)

解题思路
本解题报告版权归 Ceeji,转载请保留出处和本注释。
本人刚开始做这道题目的时候,认为这个题应该采用的方法是求连通分量。实际上后来才知道,从本质上来说就是利用欧拉回路解决问题。
把每个特征串看作图中的一条边,建立一个图。假设边数为N,如果这个图正好有一个欧拉回路(欧拉回路要求遍历所有的边,然后回到起点。),那么显然所需 要的边数为N+1。如果这个图中不存在欧拉回路,那么我们只需计算,至少需要增加的边数k,能使图中存在一个欧拉回路。则N+k就是结果。

一个有向图存在欧拉回路的充要条件是图中有且只有一个连通分量且每一点的出度等于入度。假设图中只存在一个连通分量,则至少增加的边数k=每个点出度入度之差的绝对值之和的二分之一

如果图中存在多个连通分量,则对于每个连通分量,按一个连通分支的方法求其至少的加边数,再加上本来就存在欧拉回路的连通分量的个数,就是k的值。

求连通分量,可以用广搜或者并查集(我使用了并查集),时间复杂度为O(N)。

本解题报告版权归 Ceeji,转载请保留出处和本注释。
完整代码

 
//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; 
          endVar 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 booleanFunction getFather(p:longint):longintbegin 
   if (bcj[p]=0)or(bcj[p]=p) then exit(p); 
   bcj[p]:=getFather(bcj[p]); 
   exit(bcj[p]); 
endProcedure init; 
var i,j,k:longintbegin 
    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:=0endProcedure doit(i:longint); 
var k:longintbegin 
    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; 
    endendProcedure print; 
var i,j:longintbegin 
    j:=0; 
    for i:=1 to 1000 do 
       inc(j,k[i]); 
    writeln(cn+kk+j>>1); 
    close(output); 
endbegin 
    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]=0then 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