[完善消除序列]BZOJ1006: [HNOI2008]神奇的国度
[完美消除序列]BZOJ1006: [HNOI2008]神奇的国度
Submit: 1581 Solved: 658
[Submit][Status]
1006: [HNOI2008]神奇的国度
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 1581 Solved: 658
[Submit][Status]
Description
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊,规定任意一对相互认识的人不得在一队,国王相知道,最少可以分多少支队。
Input
第一行两个整数N,M。1<=N<=10000,1<=M<=1000000.表示有N个人,M对认识关系. 接下来M行每行输入一对朋友
Output
输出一个整数,最少可以分多少队
Sample Input
4 5
1 2
1 4
2 4
2 3
3 4
1 2
1 4
2 4
2 3
3 4
Sample Output
3
HINT
一种方案(1,3)(2)(4)
Source
“该国不存在四边关系,五边关系”
也就是任何大于3的环都有一条连接不相邻节点的边
这满足了弦图的条件
然后我们就可以求最小染色数了
对于该弦图,我们做一遍完美消除序列,然后从后往前,能染就染
对于关于弦图的知识,可以参考论文:
弦图与区间图-陈丹琦
下面贴代码,第一次写弦图,可能有点渣
/************************************************************** Problem: 1006 User: SKYDEC Language: C++ Result: Accepted Time:1832 ms Memory:124112 kb ****************************************************************/ #include<stdio.h> #define MAXB 2010000 #define MAXN 10005 using namespace std; long to[MAXB],next[MAXB]; long begin[MAXN];long laber[MAXN]; long LCS[MAXN]; long n,m;bool inque[MAXN]={false}; bool use[10005][11000]={false}; void line(long a,long b,long t) { next[t]=begin[a];to[t]=b;begin[a]=t; } void find_LCS() { laber[0]=-1; for(long i=n;i>=1;i--) { long maxn=0; for(long j=1;j<=n;j++) if(!inque[j]) if(laber[j]>laber[maxn])maxn=j; LCS[i]=maxn;inque[maxn]=true; for(long k=begin[maxn];k;k=next[k]) laber[to[k]]++; } } int main() { //freopen("kingdom.in","r",stdin); //freopen("kingdom.out","w",stdout); scanf("%ld%ld",&n,&m); for(long i=1;i<=m;i++) { long a,b;scanf("%ld%ld",&a,&b); line(a,b,i*2-1); line(b,a,i*2); } find_LCS(); long ctot=0; for(long i=n;i>=1;i--) { long s=1; while(use[LCS[i]][s])s++; if(s>ctot)ctot++; use[LCS[i]][s]=true; for(long k=begin[LCS[i]];k;k=next[k]) use[to[k]][s]=true; } printf("%ld\n",ctot); //for(;;); return 0; }