题解 P4220 【[WC2018]通道】

· · 题解

人生第一道非恶评黑啊qwq

核心思想就是贪心（带一点随机）

考虑一个贪心，我们现在有一个根，显然我们想找到一个点使得两者间的三条路径长度之和最大。

但是由此产生了一个问题，我们并不知道答案中的根是哪个，所以我们有一个想法就是用这个新点来继承原来的根。

然后呢？然后就没了。

是的，接下来就不断迭代然后更新最大值就完事了。

需要注意到的是这个新点有可能以前已经被计算过了，会死循环，因此记录一个vis数组判断有没有被访问，如果被访问过了，就随机出一个没有被访问过的点。

但是关键在于我们要随机多少次呢？如何既保证正确，又保证不超时呢？我们需要一个自适应的东西。

因此我们可以使用时间函数，通过 (double)clock()/CLOCKS_PER_SEC来获取程序已经运行过的时间

控制它在3.85s内就行了

上代码qwq：

#include<bits/stdc++.h>
using namespace std;
#define _ 0
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define Set(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define debug() assert(0)
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
    T f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
    x*=f;
    return x;
}
ll rd(){ll x;rd(x);return x;}
ll n,u,v,w,nowrt=1,maxx,dep1[100005],dep2[100005],dep3[100005],ans;
bool vis[100005];
vector<pair<ll,ll> > e1[100005],e2[100005],e3[100005];
void dfs1(ll dep,ll fa){
    rep(i,0,e1[dep].size()-1){
        if(e1[dep][i].first!=fa){
            dep1[e1[dep][i].first]=dep1[dep]+e1[dep][i].second;
            dfs1(e1[dep][i].first,dep);
        }
    }
}
void dfs2(ll dep,ll fa){
    rep(i,0,e2[dep].size()-1){
        if(e2[dep][i].first!=fa){
            dep2[e2[dep][i].first]=dep2[dep]+e2[dep][i].second;
            dfs2(e2[dep][i].first,dep);
        }
    }
}
void dfs3(ll dep,ll fa){
    rep(i,0,e3[dep].size()-1){
        if(e3[dep][i].first!=fa){
            dep3[e3[dep][i].first]=dep3[dep]+e3[dep][i].second;
            dfs3(e3[dep][i].first,dep);
        }
    }
}
int main(){
    n=rd();
    rep(i,1,n-1){
        u=rd();
        v=rd();
        w=rd();
        e1[u].push_back(make_pair(v,w));
        e1[v].push_back(make_pair(u,w));
    }
    rep(i,1,n-1){
        u=rd();
        v=rd();
        w=rd();
        e2[u].push_back(make_pair(v,w));
        e2[v].push_back(make_pair(u,w));
    }
    rep(i,1,n-1){
        u=rd();
        v=rd();
        w=rd();
        e3[u].push_back(make_pair(v,w));
        e3[v].push_back(make_pair(u,w));
    }
    while(timeused()<3.85){
        while(vis[nowrt]&&timeused()<3.85) nowrt=rand()%n+1;
        vis[nowrt]=1;
        dep1[nowrt]=dep2[nowrt]=dep3[nowrt]=0;
        dfs1(nowrt,0);
        dfs2(nowrt,0);
        dfs3(nowrt,0);
        maxx=0;
        rep(i,1,n){
            if(dep1[i]+dep2[i]+dep3[i]>maxx){
                maxx=dep1[i]+dep2[i]+dep3[i];
                nowrt=i;
            }
        }
        ans=max(ans,maxx);
    }
    printf("%lld",ans);
    return ~~(0^_^0);
}