BZOJ 1006: [HNOI2008]神奇的国度(弦图)
2024-09-06 03:28:51
解题思路
弦图就是图中任意一个大小$>=4$的环至少存在一条两个节点不相邻的边,这样的图称为弦图,弦图有许多优美的性质。一个无向图是弦图当且仅当它有一个完美消除序列,完美消除序列就是一个点的排列满足$v_i$与$v_{i+1}..v_n$之间所有的边连上后的图是一个团。用最大势算法可以在$O(n+m)$内求出一个完美消除序列。做法就是设$lable(i)$表示与$i$这个点相邻的以标号节点数,每次找到未标号节点中$lable(i)$最大的一个点,而题目中的最小色数问题,在弦图中等于最小团数,为$max lable(i)+1$。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N=10005;
const int M=1000005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
}
int n,m,head[N],cnt,to[M<<1],nxt[M<<1],lable[N],best;
bool vis[N];
vector<int> v[N];
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
int main(){
n=rd(),m=rd(); int x,y,now;
for(int i=1;i<=m;i++) {
x=rd(),y=rd();
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++) v[0].push_back(i);
for(int i=n;i;i--){
while(1){
for(int j=v[best].size()-1;~j;j--){
if(!vis[v[best][j]]) {now=v[best][j];goto succ;}
v[best].pop_back();
}
--best;
}
succ:; vis[now]=1;
for(int j=head[now];j;j=nxt[j]){
int u=to[j];if(vis[u]) continue;
v[++lable[u]].push_back(u);
best=max(best,lable[u]);
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,lable[i]);
ans++; printf("%d\n",ans);
return 0;
}
最新文章
- b/s 读取多个FTP文件(图片,视频)压缩到服务器 下载到客户端
- EXCEL中汉字转大写拼音
- 关于IE9中webdiriver使用autoit上传文件报错
- Android 中this、 getApplicationContext()、getApplication()之间的区别
- nrf51822裸机教程-GPIOTE
- 【转载】图论 500题——主要为hdu/poj/zoj
- java 网络编程-tcp/udp
- MATLAB中的函数的归总
- MD5加密 Java源代码
- iOS8使用Core Graphics实现渐变效果-Swift基础教程
- [HNOI2001]求正整数
- go.js remove 特定part
- Html和Css学习笔记-css基础知识
- 安装Mycat 曾经踩的那些坑
- win10 caffe python Faster-RCNN训练自己数据集(转)
- Strange Way to Express Integers(中国剩余定理+不互质)
- 【Hive学习之五】Hive 参数&;动态分区&;分桶
- java获取上周任意一天的日期
- leetcode-746-Min Cost Climbing Stairs(动态规划)
- 在linux平台下,设置core dump文件属性(位置,大小,文件名等)
热门文章
- 2019.6.1 模拟赛——[ 费用流 ][ 数位DP ][ 计算几何 ]
- windows平台使用MongoDB shell 来连接 MongoDB 服务器并创建数据库
- 8 November in 614
- qbxt Day3 on 2019-8-18
- (62)C# 动态绑定
- Windows 08R2 IIS网站架设
- 控件识别工具Inspect.exe下载
- configure error C compiler cannot create executables错误解决
- python 类和对象上
- web前端知识体系大全【转载】