> 웹 프론트엔드 > HTML 튜토리얼 > Codeforces Round #260 (Div. 1)??Civilization_html/css_WEB-ITnose

Codeforces Round #260 (Div. 1)??Civilization_html/css_WEB-ITnose

WBOY
풀어 주다: 2016-06-24 12:00:06
원래의
1198명이 탐색했습니다.

题目链接

  • 题意:
    n个点,m条边的森林,q次操作。每次操作:1、询问x所在树的直径 2、合并x和y所在的树,使得合并后的直径最小
    (1?≤?n?≤?3·105; 0?≤?m?
  • 分析:
    没有读到图是森林。。。做的好纠结
    最开始将每个树都求一下直径,之后使用并查集处理,每次合并直径:至少是两个树的直径,或者将两个直径的最中间的部分连接求直径
  • const int MAXN = 310000;int rt[MAXN], ans[MAXN];VI G[MAXN];bool vis[MAXN];void init(int n){    REP(i, n)    {        vis[i] = false;        ans[i] = 0;        G[i].clear();        rt[i] = i;    }}int find(int n){    return n == rt[n] ? n : rt[n] = find(rt[n]);}void merge(int a, int b){    int fa = find(a), fb = find(b);    if (fa != fb)    {        rt[fa] = fb;        ans[fb] = max(ans[fb], (ans[fb] + 1) / 2 + (ans[fa] + 1) / 2 + 1);        ans[fb] = max(ans[fa], ans[fb]);    }}int Max, id;void dfs(int u, int fa, int dep){    vis[u] = true;    REP(i, G[u].size())    {        int v = G[u][i];        if (v != fa)            dfs(v, u, dep + 1);    }    if (dep > Max)    {        Max = dep;        id = u;    }}int main(){    int n, m, q;    while (~RIII(n, m, q))    {        init(n + 1);        REP(i, m)        {            int a, b;            RII(a, b);            G[a].push_back(b);            G[b].push_back(a);            int fa = find(a), fb = find(b);            rt[fa] = fb;        }        FE(i, 1, n)        {            if (!vis[i])            {                Max = -1;                dfs(i, -1, 0);                Max = -1;                dfs(id, -1, 0);                ans[find(i)] = Max;            }        }        REP(i, q)        {            int op;            RI(op);            if (op == 2)            {                int a, b;                RII(a, b);                merge(a, b);            }            else            {                int a;                RI(a);                WI(ans[find(a)]);            }        }    }    return 0;}
    로그인 후 복사


    관련 라벨:
    원천:php.cn
    본 웹사이트의 성명
    본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
    인기 튜토리얼
    더>
    최신 다운로드
    더>
    웹 효과
    웹사이트 소스 코드
    웹사이트 자료
    프론트엔드 템플릿