Codeforces734 E. Anton and Tree

传送门：>Here<

题意：给出一颗树，节点不是黑色就是白色，每次可以将一个颜色相同的块变颜色，问最少变几次才能让其变为同色

解题思路：

　　我们考虑由于每一次都是把同样颜色的色块进行变色，因此同样颜色的色块可以看成一个点。所以我们先将同一个色块缩成一个点。

　　然后我们有一个结论，我们最后的答案就是缩点完成的这棵树的直径+1再除以2.

　　我们很容易发现，缩点完成以后的树相邻的两个点颜色一定是不同的，否则就能继续缩。因此我们可以每次选择直径中间的那个点，改变它的颜色，然后它就与周围的那些点融合成为一个新的点，然后再找到中间的，继续重复如上步骤。最后我们会发现，恰好是$(dis+1) / 2$次。这个证明不是很严谨，不过感性地理解一下吧

Code

　　细节不多

/*by DennyQi*/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define  r  read()

#define  Max(a,b)  (((a)>(b))?(a):(b))

#define  Min(a,b)  (((a)<(b))?(a):(b))

using namespace std;

typedef long long ll;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

const int MOD = ;

inline int read(){

    int x = ; int w = ; register unsigned char c = getchar();

    for(; c^'-' && (c < '' || c > ''); c = getchar());

    if(c == '-') w = -, c = getchar();

    for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - '';

    return x * w;

}

int N,cur_num;

int color[MAXN],nod[MAXN],x[MAXN],y[MAXN],d[MAXN],vis[MAXN];

vector <int> g[MAXN],G[MAXN];

queue <int> q;

inline void add(int u, int v){

    g[u].push_back(v);

}

inline void Add(int u, int v){

    G[u].push_back(v);

}

void dfs(int u){

    int sz = g[u].size(),v;

    nod[u] = cur_num;

    for(int i = ; i < sz; ++i){

        v = g[u][i];

        if(!nod[v] && (color[v] == color[u])){

            dfs(v);

        }

    }

}

inline void BFS(int s){

    memset(d, 0x3f, sizeof(d));

    memset(vis,,sizeof(vis));

    d[s] = ;

    q.push(s);

    vis[s] = ;

    int u,sz,v;

    while(!q.empty()){

        u = q.front();q.pop();

        sz = G[u].size();

        for(int i = ; i < sz; ++i){

            v = G[u][i];

            if(!vis[v]){

                vis[v] = ;

                d[v] = d[u] + ;

                q.push(v);

            }

        }

    }

}

int main(){

//    freopen(".in","r",stdin);

    N=r;

    for(int i = ; i <= N; ++i){

        color[i]=r;

    }

    for(int i = ; i < N; ++i){

        x[i]=r,y[i]=r;

        add(x[i], y[i]);

        add(y[i], x[i]);

    }

    for(int i = ; i <= N; ++i){

        if(!nod[i]){

            ++cur_num;

            dfs(i);

        }

    }

    for(int i = ; i < N; ++i){

        if(nod[x[i]] != nod[y[i]]){

            Add(nod[x[i]], nod[y[i]]);

            Add(nod[y[i]], nod[x[i]]);

        }

    }

/*    for(int i = 1; i <= cur_num; ++i){

        printf("%d: ", i);

        for(int j = 0; j < G[i].size(); ++j){

            printf("%d,",G[i][j]);

        }

        printf("\n");

    }*/

    BFS();

    int _max = -,p;

    for(int i = ; i <= cur_num; ++i){

        if(d[i] > _max){

            _max = d[i];

            p = i;

        }

    }

/*    printf("p = %d\n", p);

    for(int i = 1; i <= cur_num; ++i){

        printf("%d ",d[i]);

    }

    printf("\n");*/

    BFS(p);

    _max = -;

    for(int i = ; i <= cur_num; ++i){

        if(d[i] > _max){

            _max = d[i];

        }

    }

/*    for(int i = 1; i <= cur_num; ++i){

        printf("%d ",d[i]);

    }

    printf("\n");

    printf("_max = %d\n", _max);*/

    printf("%d",(_max+)/);

    return ;

}

巴特西

Codeforces734 E. Anton and Tree

最新文章

热门文章