博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【ZOJ】1015 Fishing Net
阅读量:5874 次
发布时间:2019-06-19

本文共 1883 字,大约阅读时间需要 6 分钟。

题意:给出一个n个点的无向图,询问是否为弦图,弦图定义为对于图中任意长度>3的环一定存在环上不相邻的点有边相连(n<=1000)

#include 
using namespace std;const int N=1005;int n, m, ihead[N], cnt, tag[N], pos[N];bool vis[N];struct E { int next, to; }e[N*N];void add(int u, int v) { e[++cnt]={ihead[u], v}; ihead[u]=cnt; e[++cnt]={ihead[v], u}; ihead[v]=cnt;}void cln() { memset(ihead, 0, sizeof(int)*(n+1)); memset(tag, 0, sizeof(int)*(n+1)); memset(pos, 0, sizeof(int)*(n+1)); cnt=0;}bool check() { int x, y, mn, mx; for(int now=n; now; --now) { mx=-1; mn=~0u>>1; x=y=0; for(int i=1; i<=n; ++i) if(!pos[i] && tag[i]>mx) mx=tag[i], x=i; pos[x]=now; for(int i=ihead[x]; i; i=e[i].next) if(!pos[e[i].to]) tag[e[i].to]++; for(int i=ihead[x]; i; i=e[i].next) if(pos[e[i].to]>pos[x] && pos[e[i].to]
pos[x] && !vis[e[i].to]) return 0; for(int i=ihead[y]; i; i=e[i].next) vis[e[i].to]=0; vis[y]=0; } return 1;}int main() { while(scanf("%d%d", &n, &m), n&&m) { int x, y; for(int i=0; i

  

弦图判定裸题= =详细看cdq的论文= =《弦图与区间图》

弦图定义上边说了= =

下面来说一下性质:

团:一个完全图,即团中任意点对都有边相连。

单纯点:如果$x$及其相邻的点组成了一个团,那么$x$就是一个单纯点。

完美消除序列:一个点的序列,每个点出现有且一次,且满足对于任意$v_i$,在$v_{i+1} \cdots v_{n}$的诱导子图中$v_i$是一个单纯点。

定理1:一个弦图至少有一个完美消除序列。(证明看论文)

定理2:弦图的诱导子图也是弦图

所以裸的找完美序列的算法就是每一次找不在完美序列的点试着加入当前维护的完美序列中看是否为一个单纯点,如果是则加入。当然这是裸暴力= =

于是cdq论文介绍了两种算法= =一种是字典序bfs..一种是最大势算法,由于我看网上实现都是最大势算法(mcs算法)= =于是我就学下最大势就ok了..反正两种算法复杂度都是$O(n+m)$

首先mcs的原理是先找出一个序列然后判断这是否为一个完美消除序列。那么mcs算法是如何找出一个序列的呢?

鬼知道!反正貌似这就是一种贪心QAQcdq论文也没有解释QAQ,每一次向完美序列前面加一个点,而每次加入的点是与当前维护序列中的点连边最多的不在序列中的点= =这是什么鬼啊!

所以算法就是每一次找与序列中的点连边最多的不在序列中的点,加入= =

最后判断这个序列是否合法:

如果我们要判断$v_i$这个点,即要在$v_{i+1} \cdots v_{n}$找出与$v_i$相邻的点集$v_{j_1}, v_{j_2}, \cdots v_{j_k}$,且是按在序列的顺序从小到大的顺序。那么我们只需要判断$v_{j_1}$与$v_{j_i}, i>1$是否有边相连即可,如果没有,这个图就不是弦图。因为这是按顺序加入到序列中的,我们又要求这个点集是一个团,那么显然我们只需要判断在序列中最前面的$v_{j_1}$与其它是否相连即可,因为$v_{j_i}, i>1$都已经判断过了= =

在找连边最多的点那一步,是能用链表优化到$O(1)$的,但是我太懒了,直接暴力= =反正本题能过...就算不用$O(1)$的,我们也可以用set = =

 

转载地址:http://enzix.baihongyu.com/

你可能感兴趣的文章
经济危机下,三招实现企业网络应用最大化
查看>>
2016中国大数据应用大会将于7月召开
查看>>
高德地图上线全国最全小客车、货车限行提醒功能
查看>>
网康慧眼云发现企业网络中的XcodeGhost失陷手机
查看>>
同济吴志强:可持续发展的智慧同济校园
查看>>
网络安全老兵座谈:云安全审计(评估)应该怎么做?
查看>>
虚拟化能够满足将来的存储系统的需求
查看>>
关于weblogic配置pg和sqlserver数据源的注意事项
查看>>
从搬运工做起 动视云让游戏不再受终端束缚
查看>>
IBM系列企业云计算产品和服务正式亮相
查看>>
揭秘Pure Storage即将推出的高端阵列
查看>>
XSS Trap—XSS DNS防护的简单尝试
查看>>
TensorFlow的开源与Hadoop的开源有什么不同?
查看>>
Android使用ViewStub提高布局性能
查看>>
不玩手机的步步高玩大数据:一条短信让你多买一只澳洲大龙虾
查看>>
技术团队负责人应该具备怎样的能力
查看>>
OTT IPTV商机广阔 运营商如何进一步发掘CDN机会窗口
查看>>
使用软件定义的架构 打好IT基础
查看>>
“数”领教育山东师范大学与新华三集团开启大数据战略合作
查看>>
当一个大数据团队加入存储公司之后会发生什么?
查看>>