[HNOI2008]神奇的国度（最大势算法）

题意

给一张弦图，求它的最小染色

最小染色：将点用最少的颜色染色，使得相邻点颜色不同

弦：连接环中不相邻的两个点的边

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

具体参照这篇博客

---

思路

最大势算法

待补充

求出原图的完美消除序列，从序列的最后一个开始每次选择目前可以选的最小颜色

在本题中做法即为：初始化每个点的\(label\)值为0，每次选出一个未被选过的\(label\)值最大的点，固定它的\(label\)值，然后将与它直接连边的未被选过点的\(label\)值\(+1\)，这个过程用链表实现即可

Code:

#include<bits/stdc++.h> #define N 10005 #define M 1000005 #define Max(x,y) ((x)>(y)? (x) : (y)) using namespace std; int n,m; int label[N],nxt[N<<1],las[N<<1],best=0; bool vis[N]; struct Edge { int next,to; }edge[M<<1];int head[N],cnt=1; void add_edge(int from,int to) { edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; } template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign; } void add(int i) { nxt[i]=nxt[N+label[i]]; las[i]=N+label[i]; nxt[las[i]]=i; las[nxt[i]]=i; } void del(int i) { nxt[las[i]]=nxt[i]; las[nxt[i]]=las[i]; } int main() { read(n);read(m); for(int i=1;i<=n;++i) add(i);//全部加入0号链表 for(int i=1;i<=m;++i) { int x,y; read(x);read(y); add_edge(x,y); add_edge(y,x); } for(int i=1;i<=n;++i) { while(!nxt[best+N]) best--; int now=nxt[best+N]; del(now); vis[now]=1; for(int j=head[now];j;j=edge[j].next) { int v=edge[j].to; if(!vis[v]) { del(v); label[v]++; best=Max(best,label[v]); add(v); } } } int maxx=-1; for(int i=1;i<=n;++i) maxx=Max(maxx,label[i]); cout<<maxx+1<<endl; return 0; }

转载于:https://www.cnblogs.com/Chtholly/p/11409013.html

相关资源：JAVA上百实例源码以及开源项目