BZOJ 1006 [HNOI2008]神奇的国度

给定一个弦图，求最小染色。
题意都奥妙重重。
陈丹琦：弦图与区间图
PoPoQQQ
jcvb
vfleaking

笔记：
(0)弦图(chordal graph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦

(1)$\chi(G)$ 最小染色：用最少的颜色给点染色使相邻点颜色不同。（色数）
(2)$\alpha(G)$ 最大独立集：最大的一个点的子集使任何两个点不相邻。
(3)$\kappa(G)$ 最小团覆盖：用最少个数的团覆盖所有的点。
(4)$\omega(G)$ 最大团：点数最多的团。（团数）

(5)团数≤色数 团中的点都相邻从而颜色互不相同。
(6))最大独立集数≤最小团覆盖数 最小团覆盖的限制更为严苛，所以需要更多的数量（意识流:P）。

具体的还是看ppt吧。
图论很好玩，比如区间图。

MCS算法（最大势算法 Maximum Cardinality Search）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf (1<<30)
#define INF (1ll<<62)
#define prt cout<<#x<<":"<
#define prtn cout<<#x<<":"<
using namespace std;
typedef long long ll;
template<class T>void sc(T &x){x=0;char c;int f=1;while(c=getchar(),c<48)if(c=='-')f=-1;do x=x*10+(c^48);while(c=getchar(),c>47);x*=f;
}
template<class T>void nt(T x){if(!x)return;nt(x/10);putchar('0'+x%10);
}
template<class T>void pt(T x){if(x<0)putchar('-'),x=-x;if(!x)putchar('0');else nt(x);
}
const int maxn=10005;
const int maxm=1000005;
int n,m;
bool use[maxn];
int deg[maxn];
struct Link{int l,r;
}d[maxn<<1];int h[maxn],ecnt;
struct Edge{int to,nxt;
}e[maxm<<1];
void ins(int u,int v){e[++ecnt]=(Edge){v,h[u]};h[u]=ecnt;
}
int main(){
//  freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);sc(n);sc(m);for(int u,v,i=1;i<=m;i++){sc(u);sc(v);ins(u,v);ins(v,u);}d[1].l=n+1;d[n+1].r=1;for(int i=2;i<=n;i++){d[i].l=i-1;d[i-1].r=i;}for(int i=1;i<=n;i++)deg[i]=n+1;int ans=n+1,best=n+1;while(best>n){if(!d[best].r){best--;continue;}int p=d[best].r;use[p]=true;d[best].r=d[p].r;d[d[p].r].l=best;for(int i=h[p];i;i=e[i].nxt){int y=e[i].to;if(!use[y]){deg[y]++;if(deg[y]>best)best=deg[y];if(ansprintf("%d\n",ans-n);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！