Loading...

bzoj 1006 神奇的国度

check评论:0 条 remove_red_eye浏览量:52 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-18

链接

一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦

显然这个题目给出的是一个弦图,让你求最小染色数

那么只需要跑最大势算法求出完美消除序列即可,我只会$nlogn$的,线性的还在学习

方法大概就是,我们将所有点分为两个集合$S_A$和$S_B$,其中$S_A$代表已经选择过的点集,$S_B$代表未选择过得,每次我们从$S_B$中选择度数最大的点,这里度数指的是与多少个$S_A$中的点相邻,这个可以用大根堆维护,总复杂度$O(nlogn)$

关于弦图判定,等下再写==

#include <bits/stdc++.h>
using namespace std;
int head[10010],cnt,n,m,vis[10010],ans[10010];
struct node
{
    int ind,id;
    node(int A,int B):ind(A),id(B){}
    bool operator<(const node&a)const
    {
        return ind<a.ind;
    }
};
priority_queue<node> q;
struct edge
{
    int next,to;
}e[2000010];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        q.push(node(0,i));
    }
    while(!q.empty())
    {
        node u=q.top();
        q.pop();
        if(!vis[u.id])
        {
            vis[u.id]=1;
            for(int i=head[u.id];i;i=e[i].next)
            {
                int v=e[i].to;
                if(!vis[v])
                {
                    ans[v]++;
                    u.ind=ans[v],u.id=v;
                    q.push(u);
                }
            }
        }
    }
    int rans=0;
    for(int i=1;i<=n;i++)
    {
        rans=max(rans,ans[i]);
    }
    cout<<rans+1; 
}

deco 没有放弃

chevron_left bzoj 1242 弦图判定
bzoj 1003 物流运输 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名