首页 / 算法 / bzoj 1006 MCS算法
bzoj 1006 MCS算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了bzoj 1006 MCS算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1493字，纯文字阅读大概需要3分钟。
内容图文
根据陈丹琪的论文弦图与区间图，求出弦图的完美消除序列之后，反向给每个点染可以染的最小的颜色，这样可以使用最少的颜色染色，染色的方案即为队伍数。
那么我们需要求该图的完美消除序列，使用MCS算法，从后向前求完美消除序列，我们设size[i]为i这个点的标号，表示该点与多少个以标记的点相连，选取标号最大且i最大的点（即n）为序列的第n个，然后更新与i相连的点的标号，重复n次，即可得到弦图的完美消除序列，使用动态链表维护可以使时间复杂度达到O（m+n），暴力循环也有n^2，这道题暴力即可过。
/*
*************************************************************
Problem: 1006
User: BLADEVIL
Language: C++
Result: Accepted
Time:1720 ms
Memory:20492 kb
***************************************************************
*/
//
By BLADEVIL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
#define maxm 1000010
usingnamespace std;
int n,m,l,ans;
int peo[maxn],size[maxn],flag[maxn],color[maxn];
int last[maxm],other[maxm<<1],pre[maxm<<1];
void connect(int x,int y){
pre[++l]=last[x];
last[x]=l;
other[l]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
connect(x,y); connect(y,x);
}
for (int i=n;i;i--){
int cur=0;
for (int j=1;j<=n;j++) cur=!flag[j]&&size[j]>=size[cur]?j:cur;
flag[cur]=1; peo[i]=cur;
for (int p=last[cur];p;p=pre[p]) size[other[p]]++;
}
//for (int i=1;i<=n;i++) printf("%d ",peo[i]); printf("\n");
memset(flag,0,sizeof flag);
for (int i=n;i;i--){
for (int p=last[peo[i]];p;p=pre[p]) flag[color[other[p]]]=i;
for (color[peo[i]]=1;flag[color[peo[i]]]==i;color[peo[i]]++);
ans=max(ans,color[peo[i]]);
}
printf("%d\n",ans);
return0;
}
原文：http://www.cnblogs.com/BLADEVIL/p/3562193.html
内容总结
以上是互联网集市为您收集整理的bzoj 1006 MCS算法全部内容，希望文章能够帮你解决bzoj 1006 MCS算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。