【BZOJ1006】【HNOI2008】神奇的国度（弦图染色）

2022-10-27 22:08:38

1006: [HNOI2008]神奇的国度

Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 1467 Solved: 603
[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

Sample Output

HINT

一种方案(1,3)(2)(4)

Source

一句话题意：题意讲的有点蛋疼，这里解释一下

为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系：这句话是说给你的图中任意一个长度大于3的环上必有一条边连接环上不相邻的两个

点（弦），这样的图叫做弦图

全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。：这句话其实让你把这个弦图的点染色，使得相邻的颜色不同，且总颜色个数最少

分析：裸的弦图的染色问题：先找完美消除序列，然后把序列倒过来一个点一个点贪心染色（染当前能染的最小颜色）

code:完美消除序列的时候可以用堆找最大……这个省选前在用堆写一遍吧，顺带复习……

 #include<algorithm>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int f[maxn+],col[maxn+],label[maxn+],q[maxn+],p[maxn+];

 vector<int> g[maxn+];

 void ins(int x,int y)

 {

     g[x].push_back(y);return ;

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i) g[i].clear();

     for(int i=;i<m;++i)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         ins(x,y);ins(y,x);

     }

     memset(q,,sizeof(q));

     memset(label,,sizeof(label));

     memset(p,,sizeof(p));

     for(int i=n;i>;--i)

     {

         int m=,k=;

         for(int i=;i<=n;++i) if(label[i]>m&&p[i]==) m=label[i],k=i;

         p[k]=,q[i]=k;

         for(int i=;i<g[k].size();++i) ++label[g[k][i]];

     }

     memset(col,,sizeof(col));

     memset(f,,sizeof(f));

     int ans=;

     for(int k=n;k>;--k)

     {

         for(int i=;i<g[q[k]].size();++i) f[col[g[q[k]][i]]]=k;

         int j;

         for(j=;j<=n;++j) if(f[j]!=k) break;

         col[q[k]]=j;

         ans=max(ans,j);

     }

     printf("%d",ans);

     return ;

 }

码农公寓