POI 2001 Peaceful Commission 和平委员会

This post is written in Chinese. Please consider using Google Translate

把每个政党的两个议员看作两个顶点,不能相处的议员之间连接一条边。类似于二分图的染色,但又不是严格的二分图。我们规定第2i-1和2i个顶 点为姊妹顶点。对于图中的每个连通分量,尝试从首个顶点开始访问染色,规定其加入理事会,然后访问该顶点的邻接顶点的姊妹顶点。遍历中如果发现了一对姊妹 顶点都被加入了理事会,则是不合法的,染色失败。如果染色成功,继续查找下一个连通分量,否则重新尝试从首个顶点的姊妹顶点开始访问染色,如果染色成功, 继续查找下一个连通分量,否则染色失败,不可能组建理事会。

该算法巧妙的类比了二分图染色,并根据该题的特点,设计出合适的方案,时间复杂度为O(M)。

/* 
 * Problem: POI2001 spo
 * Author: Guo Jiabao
 * Time: 2009.1.28 0:58
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=16001,MAXM=36001;

struct list
{
    list *next;
    int t;
};

struct adjl
{
    list *f,*l;
};

adjl A[MAXN];
list L[MAXM];
int N,M,Lc;
bool S[MAXN],TS[MAXN];

void addedge(int a,int b)
{
    if (A[a].f)
        A[a].l=A[a].l->next=&L[++Lc];
    else
        A[a].l=A[a].f=&L[++Lc];
    L[Lc].t=b;
}

void init()
{
    int i,a,b;
    freopen("spo.in","r",stdin);
    freopen("spo.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
}

inline int getop(int k)
{
    if (k%2) return k+1;
    else return k-1;
}

bool deal(int a)
{
    int b,bo,ao;
    S[a]=true;
    ao=getop(a);
    if (S[ao])
        return false;
    for (list *k=A[a].f;k;k=k->next)
    {
        b=k->t;
        bo=getop(b);
        if (!S[bo] && !deal(bo))
            return false;
    }
    return true;
}

void print(bool k)
{
    if (k)
    {
        for (int i=1;i<=N*2;i++)
            if (S[i])
                printf("%dn",i);
    }
    else
        printf("NIEn");
}

void cpy(bool *A,bool *B)
{
    for (int i=1;i<=N*2;i++)
        B[i]=A[i];
}

bool solve(int k)
{
    if (!deal(k))
    {
        cpy(TS,S);
        if (!deal(k+1))
            return false;
    }
    cpy(S,TS);
    return true;
}

void compute()
{
    for (int i=1;i<=N*2;i+=2)
    {
        if (S[i]==0)
        {
            if (!solve(i))
            {
                print(false);
                return;
            }
        }
    }
    print(true);
}

int main()
{
    init();
    compute();
    return 0;
}
<h2><span class="mw-headline">和平委员会 </span></h2>

根据宪法,Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是,由于某些党派代表之间的不和睦而使得这件事存在障碍。

此委员会必须满足下列条件:
  • 每个党派都在委员会中恰有1个代表,
  • 如果2个代表彼此厌恶,则他们不能都属于委员会。

    每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第I个党派。

    任务

    写一程序:

  • 从文本文件读入党派的数量和关系不友好的代表对,

  • 计算决定建立和平委员会是否可能,若行,则列出委员会的成员表,
  • 结果写入文本文件。

    输入

    在文本文件的第一个行有2非负整数n和m。 他们各自表示:党派的数量n,1 < =n < =8000和不友好的代表对m,0 <=m <=20000。 在下面m行的每行为一对整数a,b,1<=a <b<=2n,中间用单个空格隔开。 它们表示代表a,b互相厌恶。

    输出

    如果委员会不能创立,文本文件中应该包括单词NIE。若能够成立,文本文件SPO.OUT中应该包括n个从区间1到2n选出的整数,按升序写出,每行一个,这些数字为委员会中代表的编号。如果委员会能以多种方法形成,程序可以只写他们的某一个。

    样品输入

    3 2
      1 3
      2 4
    样品输出
    1
      4
      5

Related posts