Bakser's Blog

我是逗比。

bzoj1006 弦图的最小染色

| Comments

今天将夜也完本了好悲桑啊啊啊,结局还是很带感的。
书荒了QAQ
今天丧病的去捉弦图,发现智商受到了挑战。
当然要看cdq的课件,讲的还是很清楚的,就是理解起来莫名逗比。
然后这道题就是例题。
那啥题目里说不能有四边关系。
其实就是说是个弦图啦。
然后最小染色数等于最大团的点数,关于为什么,有一份非常神犇的证明
然后写的时候发现你确定mcs不是n^2+m的?
找最大值神马的怎么看也不可能是O(1)的。
于是逗比良久,然后想出了一个机智的做法,
就像课件里讲的字典序bfs的做法一样,对于label值维护好多个桶(list),然后各种修改,查询似乎成功的降到了常数级。
被自己的机智深深的感动了,然后去写nlogn+m的堆优化去了。
由于太颓废了,懒得写机智的n+m做法了。
有愿意写出来的请通知我。。。。

bzoj1005
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 10100
#define MAX(a,b) (((a)>(b))?(a):(b))
typedef pair<int,int> pii;
struct hh
{
    int v,next;
}edges[2000100];
int n,m,point[N],seq[N],pos[N],label[N],ans;
bool used[N];
inline void addedge(int u,int v)
{
    static int en(0);
    edges[++en].next=point[u];
    edges[en].v=v;
    point[u]=en;
}
inline void mcs()
{
    static priority_queue<pii> q;
    for(int i=1;i<=n;i++)
        q.push(make_pair(0,i));
    for(int i=n;i>=1;i--)
    {
        while(used[q.top().second])q.pop();
        int u(q.top().second);
        seq[i]=u;pos[u]=i;used[u]=1;
        for(int i=point[u];i;i=edges[i].next)
            if(!used[edges[i].v])
                q.push(make_pair(++label[edges[i].v],edges[i].v));
    }
    for(int i=1;i<=n;i++)
    {
        int sum(0);
        for(int j=point[i];j;j=edges[j].next)
            if(pos[edges[j].v]>pos[i])
                sum++;
        ans=MAX(ans,sum+1);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0,u,v;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    mcs();
    printf("%d\n",ans);
    return 0;
}

Comments

comments powered by Disqus