BZOJ1006 神奇的国度 【弦图染色——最大势算法MCS】
2024-09-02 02:21:02
1006: [HNOI2008]神奇的国度
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 4146 Solved: 1916
[Submit][Status][Discuss]
Description
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA
相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2
...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C
D,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
1 2
1 4
2 4
2 3
3 4
Sample Output
3
HINT
一种方案(1,3)(2)(4)
论文链接:弦图与区间图——陈丹琦
身为蒟蒻,上来直接dfs染色,无悬念WA
百度一查,原来染色问题是NP完全的。。。QAQ
而由于本图的性质,有一个神奇的算法可以在O(n + m)时间内解决【似乎本题O(nlogn)更好?】
一开始标上每个点为0,每次选一个未访问值最大的点染上最小能染的颜色,并将与它相连的点+1
最后就能求出结果
【读论文读了一晚上QAQ】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 10005,maxm = 2000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
}
int n,m,c[maxn],co[maxn],d[maxn],siz = 0;
int head[maxn],h[maxn],nedge = 0,ln = 0;
struct EDGE{int to,next;}edge[maxm],list[maxm];
inline void build(int u,int v){
edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;
edge[nedge] = (EDGE){u,head[v]}; head[v] = nedge++;
}
void MCS(){
REP(i,n) list[ln] = (EDGE){i,h[0]},h[0] = ln++;
int best = 0,u,to;
for (int i = 1; i <= n; i++){
while (true){
u = -1;
for (int& k = h[best]; k != -1; k = list[k].next)
if (!c[list[k].to]){u = list[k].to; break;}
if (u < 0) best--;
else break;
}
Redge(u){
if (c[to = edge[k].to]) co[c[to]] = u;
d[to]++; list[ln] = (EDGE){to,h[d[to]]}; h[d[to]] = ln++;
best = max(best,d[to]);
}
REP(i,siz) if (co[i] != u) {c[u] = i; break;}
if (!c[u]) c[u] = ++siz;
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(h,-1,sizeof(h));
n = read(); m = read();
while (m--) build(read(),read());
MCS();
cout<<siz<<endl;
return 0;
}
最新文章
- sprint3冲刺总结
- C 结构体小结
- Cadence ORCAD CAPTURE元件库介绍
- vm上安装ubuntu
- A1486. 树(王康宁)
- html5 之 canvas 相关知识(三)API-strokeStyle-shadow相关
- 【POJ2773】Happy 2006 欧几里德
- 【转】Apache 关于 mod_rewrite 遇到 %2F或%5C (正反斜杠)等特殊符号导致URL重写失效出现404的问题
- 字典dict
- 设计模式のPrototypePattern(原型模式)----创建模式
- Google&#39;s Machine Learning Crash Course #04# First Steps with TensorFlow
- 01:saltstack 基本使用
- [C语言]数据类型与计算
- SSIS 剖析数据流之:连接和查找转换
- VueJS 数据驱动和依赖追踪分析
- Spring DBCP用xml和properties2种格式配置DataSource
- Gearman简介
- JavaScript权威指南--WEB浏览器中的javascript
- Ubuntu + apache + Mysql +php
- TF随笔-3
热门文章
- Linux命令应用大词典-第24章 任务计划
- [JSON].result()
- gitolite 丢失管理密钥/访问权限 解决办法
- kosaraju求强连通分量
- Centos配置深度学习开发环境
- LeetCode - 442. Find All Duplicates in an Array - 几种不同思路 - (C++)
- Bad Cowtractors(最大生成树)
- 搭建独立域名博客 -- 独立域名博客上线了 www.hanshuliang.com
- (七)类、超类和子类 ——(多态,动态绑定,final类,类型转换,抽象类)
- 转 Redis集群技术及Codis实践