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

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:完美消除序列的时候可以用堆找最大……这个省选前在用堆写一遍吧，顺带复习……

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn=10000;
 7 int f[maxn+50],col[maxn+50],label[maxn+50],q[maxn+50],p[maxn+50];
 8 vector<int> g[maxn+50];
 9 void ins(int x,int y)
10 {
11     g[x].push_back(y);return ;
12 }
13 int main()
14 {
15     int n,m;
16     scanf("%d%d",&n,&m);
17     for(int i=0;i<=n;++i) g[i].clear();
18     for(int i=0;i<m;++i)
19     {
20         int x,y;
21         scanf("%d%d",&x,&y);
22         ins(x,y);ins(y,x);
23     }
24     memset(q,0,sizeof(q));
25     memset(label,0,sizeof(label));
26     memset(p,0,sizeof(p));
27     for(int i=n;i>0;--i)
28     {
29         int m=0,k=1;
30         for(int i=1;i<=n;++i) if(label[i]>m&&p[i]==0) m=label[i],k=i;
31         p[k]=1,q[i]=k;
32         for(int i=0;i<g[k].size();++i) ++label[g[k][i]];
33     }
34     memset(col,0,sizeof(col));
35     memset(f,0,sizeof(f));
36     int ans=0;
37     for(int k=n;k>0;--k)
38     {
39         for(int i=0;i<g[q[k]].size();++i) f[col[g[q[k]][i]]]=k;
40         int j;
41         for(j=1;j<=n;++j) if(f[j]!=k) break;
42         col[q[k]]=j;
43         ans=max(ans,j);
44     }
45     printf("%d",ans);
46     return 0;
47 }

View Code