首页 > 代码库 > SPOJ TWOPATHS Two Paths

SPOJ TWOPATHS Two Paths

2024-07-14 20:25:47   220人阅读

　　题目意思：给一棵树，找到俩个不相交的通路，使得这俩个通路的长度和乘机最大；

解法：

　　小哥一看呵呵 这不就是枚举点 然后求俩边的树的直径在相乘求个最大值的题么！

　　呵呵 这个N 有100000 当时就不玩了；

　　学长指导了下我；

　　俺会了！/灯泡

　　在枚举点在书的直径上时点的左右的最长的链无非这几种情况如图（红色是树得直径）（蓝色和绿色是俩种情况）

　　无非就 蓝色和绿色这个俩种，所以这个答案和直径有很大的关系！

不在直径上时：一边肯定是直径了另一半呢？如图；

 

　　解的过程：

　　　　1: 想求出直径的点顺序的 存在一个数组内；

　　　　2: 求出和每个直径上节点相邻的  最大和次大 和直径不相连的  链的 长度  并求出Max（这个链的点都不在直径上）

　　　　3：O（n）枚举点并求出这个点的左右的长度最值

　　　　4：由3的结果求出最大的ANS ，在和树得直径*Max取最值

　　over：

代码

#include <cstring>#include <algorithm>#include <cmath>#include <cstdio>#include <cstdlib>using namespace std;const int INF=0x7fffffff;const int maxn=100002;struct Edge{    int to,pre;    Edge (int to=0,int pre=0):to(to),pre(pre){}};Edge edge[maxn*2];int head[maxn],pos;bool vis[maxn];bool in_line[maxn];int ko[maxn],pos_ko;int dp[maxn][2];int dp1[maxn],dp2[maxn];struct info{    int p,pre;};info  que[maxn];void inint(){    memset(head,-1,sizeof(head));    pos=pos_ko=0;    memset(dp,0,sizeof(dp));    memset(in_line,false,sizeof(in_line));    memset(dp1,0,sizeof(dp1));    memset(dp2,0,sizeof(dp2));}void add_edge(int s,int to){    edge[pos]=Edge(to,head[s]);    head[s]=pos++;}void make(int P){    if(que[P].pre!=-1)make(que[P].pre);    ko[pos_ko++]=que[P].p;    in_line[que[P].p]=true;}int bfs(int t,bool flag){    memset(vis,false,sizeof(vis));    int h=0,r=1;    que[0].p=t;    que[0].pre=-1;    vis[t]=true;    int x;    while(h<r)    {        x=que[h++].p;        for(int i=head[x];~i;i=edge[i].pre)        {            Edge &tmp=edge[i];            if(!vis[tmp.to])                que[r].p=tmp.to,                que[r++].pre=h-1,                vis[tmp.to]=true;        }    }    if(flag)make(r-1);    return que[r-1].p;}void get_it(int key,int t){    if(key>dp[t][0])dp[t][1]=dp[t][0],                    dp[t][0]=key;    else if(key>dp[t][1])                    dp[t][1]=key;}int Max;int dfs(int pa,int &s,int &t){    int key,ans=0;    for(int w=head[s];~w;w=edge[w].pre)    {        Edge &tmp=edge[w];        if(tmp.to==pa||in_line[tmp.to])continue;        key=dfs(s,tmp.to,t);        if(pa==-1) get_it(key,t);        if(pa!=-1)        {            if(ans)                Max=max(Max,ans-1+key);            else                Max=max(Max,key);        }        ans=max(ans,key+1);    }    if(pa==-1)Max=max(Max,ans-2);    return ans==0?1:ans;}void solve(int &n){    long long  ans=0;    Max=0;    int p1=bfs(1,false),p2=bfs(p1,true);    int Max1;    for(int i=0;i<pos_ko;i++)        dfs(-1,ko[i],i);    ans=(pos_ko-1)*Max;    --pos_ko;    for(int i=1;i<pos_ko;i++)    {        dp1[i]=max(dp1[i-1],i+dp[i][0]);        dp1[i]=max(dp1[i],dp[i][0]+dp[i][1]);    }    for(int i=pos_ko-1;i>=0;i--)    {        dp2[i]=max(dp2[i+1],pos_ko-i+dp[i][0]);        dp2[i]=max(dp2[i],dp[i][0]+dp[i][1]);    }    for(int i=1;i<pos_ko;i++)        ans=max(ans,(long long)dp1[i]*dp2[i+1]);    ans=max(ans,(long long )0);    printf("%lld\n",ans);}int main(){    int n;    int a,b;    while(~scanf("%d",&n))    {        inint();        for(int i=2;i<=n;i++)        {            scanf("%d%d",&a,&b);            add_edge(a,b);            add_edge(b,a);        }        solve(n);    }    return 0;}

 


联系
我们