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)

相关日志