POI 1999 遺傳密碼 Primitivus

把特徵串看作圖中的一條邊，建立一個圖。我們只需計算，至少增加的邊數k，能使圖中存在一個歐拉回路，則N+k就是結果。

一個有向圖存在歐拉回路的充要條件是圖中有且只有一個連通分支且每一點的出度等於入度。假設圖中只存在一個連通分支，則至少增加的邊數k＝每個點出度入度之差的絕對值之和的二分之一。

如果圖中存在多個連通分支，則對於每個連通分支，按一個連通分支的方法求其至少的加邊數，再加上本來就存在歐拉回路的連通分支的個數，就是k的值。

求連通分量的方法可以用廣搜或者並查集，時間複雜度爲O(N)。

/* 
 * Problem: POI1999 pie
 * Author: Guo Jiabao
 * Time: 2008.12.15 22:00:54
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1001;

class tUFS
{
    public:
    int F[MAXN];
    tUFS()
    {
        for (int i=1;i<MAXN;i++)
            F[i]=-i;
    }
    int findroot(int a)
    {
        int r=a,t;
        while (F[r]>0) r=F[r];
        while (F[a]>0) {t=F[a];F[a]=r;a=t;}
        return r;
    }
    void Union(int a,int b)
    {
        F[findroot(a)]=findroot(b);
    }
    bool Judge(int a,int b)
    {
        return F[findroot(a)]==F[findroot(b)];
    }
    int getroot(int a)
    {
        return -F[findroot(a)];
    }
};

int M,PC,Ans;
int ind[MAXN],oud[MAXN];
bool app[MAXN],P[MAXN];
int A[MAXN],Q[MAXN];
tUFS U;

void init()
{
    int i,a,b;
    freopen("pie.in","r",stdin);
    freopen("pie.out","w",stdout);
    scanf("%d",&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        oud[a]++; ind[b]++;
        app[a]=app[b]=true;
        if (!U.Judge(a,b))
            U.Union(a,b);
    }
}

void solve()
{
    int i,k,v;
    for (i=1;i<MAXN;i++)
    {
        if (app[i])
        {
            k=U.getroot(i);
            if (!P[k])
            {
                P[k]=true;
                Q[++PC]=k;
            }
            v=ind[i]-oud[i]; if (v<0) v=-v;
            A[k]+=v;
        }
    }
    Ans=M;
    if (PC==(i=1))
    {
        if (A[Q[i]]==0)
            Ans++;
        else
            Ans+=A[Q[i]]/2;
    }
    else
    {
        for (i=1;i<=PC;i++)
        {
            if (A[Q[i]]==0)
                Ans++;
            else
                Ans+=A[Q[i]]/2;
        }
    }
}

int main()
{
    init();
    solve();
    printf("%d",Ans);
    return 0;
}

<h2><span class="mw-headline">遺傳密碼</span></h2>

問題描述

一個 primitivus 的 遺傳密碼 是一串自然數 K= ( a_1,...,a_n ) 。所有在 primitivus 的遺傳密碼中連續出現的數對 ( l , r ) 被稱爲一個 primitivus 的 特徵 。例如存在一個 i ， l=a_i, r=a_i+1 。在 primitivus 的遺傳密碼中沒有形如 ( p , p ) 的特徵。 任務

寫一個程序
  • 從輸入文件中讀入特徵的列表
  • 計算 primitivus 的遺傳密碼的最短長度

  • 將結果寫到輸出文件

    輸入格式

    在輸入文件的第一行有一個正整數 n ，表示 primitivus 的遺傳密碼的不同的特徵。在接下來的 n 行中，每行有一對自然數 l 和 r ，用空格隔開， 1 <= l <= 1000, 1 <= r <= 1000 。數對 ( l , r ) 是 primitivus 的特徵。特徵不會在輸入文件中重複出現。

    輸出格式

    你的程序應當向輸出文件輸出一個數，表示包含輸入文件中所有特徵的最短的 primitivus 遺傳密碼的長度。

    輸入樣例

    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
    註釋 下面的遺傳密碼包含了所有特徵： 
    (8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)

相關日誌