【dfs+理解题意+构造】【待重做】codeforces E. Ice cream coloring

http://codeforces.com/contest/805/problem/E

【题意】

染色数是很好确定，最少染色数是max(si)（最小为1，即使所有的si都为0，这样是单节点树形成的森林需要1种颜色），关键是确定染色方案。

一开始没看出来树有什么用，但其实一句话很关键：Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.

也就是说在原来的图中，含有相同的冰淇淋的点是一个联通子图。那么比如1，2在一个点，1，3在一个点，那么2，3便不可能在另一个点了，因为那样将会形成一个环，也就是说这个图不再是树了。

“因为每种冰淇淋所在的所有点在这颗树上是一个连通块，也就是说，沿着树搜索下去，不可能出现已经染过色且父亲中没有的冰淇淋重新出现的问题。于是就可以直接贪心构造一波就行了。” 然而这里还是每太明白，为什么这样构造......

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 int n,m;

 const int maxn=3e5+;

 vector<int> s[maxn];

 int num[maxn];

 int c[maxn];

 struct node

 {

     int to;

     int nxt;

 }edge[maxn<<];

 int head[maxn];

 int tot;

 int res;

 void add(int u,int v)

 {

     edge[tot].nxt=head[u];

     edge[tot].to=v;

     head[u]=tot++;

 }

 void Init()

 {

     res=;

     tot=;

     memset(c,,sizeof(c));

     memset(head,-,sizeof(head));

 }

 void dfs(int u,int pre)

 {

     res=max(res,num[u]);

     set<int> t;

     t.clear();

     for(int i=;i<num[u];i++)

     {

         int v=s[u][i];

         if(c[v])

         {

             t.insert(c[v]);

         }

     }

     int temp=;

     for(int i=;i<num[u];i++)

     {

         int v=s[u][i];

         if(!c[v])

         {

             temp++;

             while(t.count(temp))

             {

                 temp++;

             }

             c[v]=temp;

         }

     }

     for(int i=head[u];i!=-;i=edge[i].nxt)

     {

         int to=edge[i].to;

         if(to!=pre)

         {

             dfs(to,u);

         }

     }

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         Init();

         for(int i=;i<=n;i++)

         {

             scanf("%d",&num[i]);

             s[i].clear();

             for(int k=;k<num[i];k++)

             {

                 int x;

                 scanf("%d",&x);

                 s[i].push_back(x);

             }

         }

         int u,v;

         for(int i=;i<n-;i++)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         dfs(,);

         for(int i=;i<=m;i++)

         {

             if(!c[i])

             {

                 c[i]=;

             }

         }

         cout<<res<<endl;

         cout<<c[];

         for(int i=;i<=m;i++)

         {

             cout<<" "<<c[i];

         }

         cout<<endl;

     }

     return ;

  }

巴特西

【dfs+理解题意+构造】【待重做】codeforces E. Ice cream coloring

最新文章

热门文章