洛谷 P4408 [NOI2003] 逃学的小孩题解

Analysis

题意虽然说先去谁家再去谁家，但是我们不需要管这个，因为AA、BB、CC三个点我们可以任意互相交换它们所代表的对象，所以题目要求的就是在一棵树上找到3个点AA、BB、CC令AB+BCAB+BC最大，同时要满足AC>ABAC>AB。

由于这是一棵树，它满足非常可爱的性质，就是如果找一个点出去两条路径使它们的合最大，那么一条是直径时一定会存在一种最大的方案。

所以我们可以使要找的两条路径其中一条是直径（设为ABAB），然后枚举剩下的点，找到一个到达直径端点最长的另一条路径，不过因为题目要满足一个AC>ABAC>AB，所以我们需要在每次枚举的时候（设为CC），选择ACAC和BCBC的较小的一条边作为另一条路径。可以看到，若是ACAC是小于BCBC的，则选择的路径是ACAC，实际走的路线是CACA+ABAB，满足题目要求的CA<CBCA<CB，而若是选择的是BCBC，实际路线是CBCB+BABA，也符合题意要求的CB<CACB<CA。

至此，就可以写出代码了，跑2遍dfs找出直径，再对直径起点和终点跑出对每个点的路径长度，然后计算答案。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define maxn 200000+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

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

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,m,cnt,com,sta,ed,ans;

 int dis1[maxn],dis2[maxn],head[*maxn];

 struct node

 {

     int to,val,nxt;

 }edge[*maxn];

 inline void add(int x,int y,int z)

 {

     cnt++;

     edge[cnt].to=y;

     edge[cnt].val=z;

     edge[cnt].nxt=head[x];

     head[x]=cnt++;

 }

 inline void dfs1_tree_d(int x,int fa)

 {

     for(int i=head[x];i;i=edge[i].nxt)

     {

         int to=edge[i].to;

         if(to==fa) continue;

         dis1[to]=dis1[x]+edge[i].val;

         if(dis1[to]>com)

         {

             com=dis1[to];

             sta=to;

         }

         dfs1_tree_d(to,x);

     }

 }

 inline void dfs2_tree_d(int x,int fa)

 {

     for(int i=head[x];i;i=edge[i].nxt)

     {

         int to=edge[i].to;

         if(to==fa) continue;

         dis2[to]=dis2[x]+edge[i].val;

         if(dis2[to]>com)

         {

             com=dis2[to];

             ed=to;

         }

         dfs2_tree_d(to,x);

     }

 }

 inline void find1_long(int x,int fa)

 {

     for(int i=head[x];i;i=edge[i].nxt)

     {

         int to=edge[i].to;

         if(to==fa) continue;

         dis1[to]=dis1[x]+edge[i].val;

         find1_long(to,x);

     }

 }

 inline void find2_long(int x,int fa)

 {

     for(int i=head[x];i;i=edge[i].nxt)

     {

         int to=edge[i].to;

         if(to==fa) continue;

         dis2[to]=dis2[x]+edge[i].val;

         find2_long(to,x);

     }

 }

 signed main()

 {

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

 //    freopen("truant.out","w",stdout);

     n=read();m=read();

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

     {

         int x=read(),y=read(),z=read();

         add(x,y,z);

         add(y,x,z);

     }

     com=;

     dfs1_tree_d(,);

     com=;

     dfs2_tree_d(sta,);

     ans=dis2[ed];

     memset(dis1,,sizeof(dis1));

     memset(dis2,,sizeof(dis2));

     find1_long(sta,);

     find2_long(ed,);

     com=;

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

     {

         int len=min(dis1[i],dis2[i]);

         if(len>com) com=len;

     }

     ans+=com;

     write(ans);

     return ;

 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

巴特西

洛谷 P4408 [NOI2003] 逃学的小孩题解

Analysis

最新文章

热门文章

巴特西

洛谷 P4408 [NOI2003] 逃学的小孩 题解

Analysis

最新文章

热门文章

洛谷 P4408 [NOI2003] 逃学的小孩题解