BZOJ 1006: [HNOI2008]神奇的国度（弦图染色）

浅浅的花香味﹌ 2021-12-11 08:41 268阅读 0赞

[http://www.lydsy.com/JudgeOnline/problem.php?id=1006][http_www.lydsy.com_JudgeOnline_problem.php_id_1006]

题意：  
![1047463-20170805100041725-2110388376.jpg][]

思路：

这个就是弦图染色问题，弦图啥的反正我也不懂，具体看论文[https://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html][https_wenku.baidu.com_view_07f4be196c175f0e7cd13784.html]

这里的话就是用最大势算法求了一个完美消除序列，然后根据完美消除序列来进行染色即可。

1 #include<iostream>
     2 #include<algorithm>
     3 #include<cstring>
     4 #include<cstdio>
     5 #include<sstream>
     6 #include<vector>
     7 #include<stack>
     8 #include<queue>
     9 #include<cmath>
    10 #include<map>
    11 #include<set>
    12 using namespace std;
    13 typedef long long ll;
    14 typedef pair<int,ll> pll;
    15 const int INF = 0x3f3f3f3f;
    16 const int maxn=10000+5;
    17 
    18 int n, m;
    19 int head[maxn];
    20 int tot;
    21 int ans;
    22 int label[maxn]; //label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号
    23 int vis[maxn];
    24 int q[maxn];
    25 int check[maxn];
    26 int col[maxn];
    27 
    28 struct node
    29 {
    30     int v;
    31     int next;
    32 }e[2*1000000+1000];
    33 
    34 void addEdge(int u, int v)
    35 {
    36     e[tot].v=v;
    37     e[tot].next=head[u];
    38     head[u]=tot++;
    39 }
    40 
    41 void MCS()  //最大势算法求完美消除序列
    42 {
    43     memset(vis,0,sizeof(vis));
    44     for(int i=n;i;i--)
    45     {
    46         int pos=0;
    47         for(int j=1;j<=n;j++)   //选择当前未访问且label值最大的
    48             if(!vis[j] && label[j]>=label[pos])   pos=j;
    49         vis[pos]=1;
    50         q[i]=pos;
    51         for(int j=head[pos];j!=-1;j=e[j].next)  //与pos结点相邻的结点label值+1
    52             label[e[j].v]++;
    53     }
    54 }
    55 
    56 void color()//染色
    57 {
    58     memset(check,0,sizeof(check));
    59     memset(col,0,sizeof(col));
    60     for(int i=n;i;i--)
    61     {
    62         int pos=q[i],j;
    63         for(int j=head[pos];j!=-1;j=e[j].next)  check[col[e[j].v]]=i;
    64         for(j=1;;j++)  if(check[j]!=i)  break;
    65         col[pos]=j;
    66         if(j>ans)  ans=j;
    67     }
    68 }
    69 
    70 int main()
    71 {
    72     //freopen("in.txt","r",stdin);
    73     while(~scanf("%d%d",&n,&m))
    74     {
    75         tot=0;
    76         memset(head,-1,sizeof(head));
    77         while(m--)
    78         {
    79             int u,v;
    80             scanf("%d%d",&u,&v);
    81             addEdge(u,v);
    82             addEdge(v,u);
    83         }
    84         ans=0;
    85         MCS();
    86         color();
    87         printf("%d\n",ans);
    88     }
    89     return 0;
    90 }

转载于:https://www.cnblogs.com/zyb993963526/p/7289337.html

[http_www.lydsy.com_JudgeOnline_problem.php_id_1006]: http://www.lydsy.com/JudgeOnline/problem.php?id=1006
[1047463-20170805100041725-2110388376.jpg]: /images/20211211/7224a7c052ef4d899fd0df068af07c5f.png
[https_wenku.baidu.com_view_07f4be196c175f0e7cd13784.html]: https://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html