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