cf14D Two Paths（树的直径）

题意：

N个点构成一棵树。树枝的长度都是1。

在当中找两条不相交【没有公共点】的路，使得二者长度之积最大。

(2 ≤ n ≤ 200)

思路：

一开始思路好麻烦，好麻烦，好麻烦，，，，，，，而且WA，，，，，

正解：

必定存在第三条路径连接两条最长路径。【因为是一棵树】。

去掉第三条路径上的某根树枝就可以将原树分成两个区域了，两条最长路径分别在一个区域里。

然后分别求两个区域的直径，相乘。

N不大，枚举。

代码：

int const N=210;

int n;

vector<int> G[N];

int g[N][N];

queue<int> Q;

int vis[N];

void Input(){

    cin>>n;

    mem(g,0);

    rep(i,1,n) G[i].clear();

    rep(i,1,n-1){

        int a,b;

        scanf("%d%d",&a,&b);

        G[a].push_back(b);

        G[b].push_back(a);

        g[a][b]=1;

        g[b][a]=1;

    }

}

int path(int x){ //从x出发，求直径

    mem(vis,-1);

    while(!Q.empty()) Q.pop();

    Q.push(x);

    vis[x]=0;

    while(!Q.empty()){

        int u=Q.front();    Q.pop();

        int L=G[u].size();

        rep(i,0,L-1){

            int v=G[u][i];

            if(g[u][v]==1 && vis[v]==-1){

                vis[v]=vis[u]+1;

                Q.push(v);

            }

        }

    }

    int ans=-1;

    int vv=-1;

    rep(i,1,n){

        if(vis[i]>ans){

            ans=vis[i];

            vv=i;

        }

    }

    while(!Q.empty()) Q.pop();

    mem(vis,-1);

    Q.push(vv);

    vis[vv]=0;

    while(!Q.empty()){

        int u=Q.front();    Q.pop();

        int L=G[u].size();

        rep(i,0,L-1){

            int v=G[u][i];

            if(g[u][v]==1 && vis[v]==-1){

                vis[v]=vis[u]+1;

                Q.push(v);

            }

        }

    }

    ans=-1;

    rep(i,1,n){

        if(vis[i]>ans){

            ans=vis[i];

        }

    }

    return ans;

}

void Solve(){

    int ans=0;

    rep(i,1,n-1){

        rep(j,i+1,n){

            if(g[i][j]==1){

                g[i][j]=g[j][i]=0;

                int x1=path(i);

                int x2=path(j);

                ans=max(ans,x1*x2);

                g[i][j]=g[j][i]=1;

            }

        }

    }

    printf("%d\n",ans);

}

int main(){

    Input();

    Solve();

    return 0;

}

巴特西

cf14D Two Paths（树的直径）

最新文章

热门文章