【bzoj1006】[HNOI2008]神奇的国度

2015.04.20 20:41 Mon | 3次阅读 | 旧日oi | 固定链接 | 源码

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

3

HINT

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

题解

http://wenku.baidu.com/link?url=kxOBTVlriFErpG9tfypEtig9kCCZr3R-pyqU4dbqNlD0sOCOs7gWOz5J5GLlgoo_OQ5YveDwByYnPEfQ2FW5Z2Px0dhd5IhG20HQZrggQ7u
看懂了这些之后就应该很好做了,当然看不懂的话理解了大概咋回事也能写出来……话说hnoi2008怎么这么多鬼畜的知识点……

我的程序

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct  edge
{
    int to;
    int next;
}e[2000005];
int h[10005],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int d[10005],c[10005],use[10005],q[10005];
bool vis[10005];
int main()
{
    //freopen("1006.in", "r", stdin);
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    /*最大势算法,每次找出d值最大同时编号最大的点
    ,从后往前记录,得到的就是一个完美消除序列*/
    for(int i=n;i;i--)
    {
        int tmp=0;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&d[j]>=d[tmp]) tmp=j;
        vis[q[i]=tmp]=1;
        for(int j=h[tmp];e[j].to;j=e[j].next)
            d[e[j].to]++;
    }
    int ans=0;
    /*从后往前依次枚举每一个点u,再枚举和u相邻的点,
    用这些点找到每次能给u染的最小颜色,最后所有点中的最大颜色就是答案*/
    for(int i=n;i;i--)
    {
        int u=q[i],j;
        for(int j=h[u];e[j].to;j=e[j].next)
            use[c[e[j].to]]=i;
        for(j=1;j<=n&&use[j]==i;j++);
            c[u]=j;
        if(c[u]>ans) ans=c[u];
    }
    printf("%d\n",ans);
}```