牛客月赛27

牛客月赛27

A

题意：
就是给你一个连通图，然后从一个点遍历整张图的花费就是走完所有点中途路径的花费。现在问你每个点都可以作为起点，问你最多可以选择多少个起点使得所有的花费总和不超过m。

思考：
明显只要知道一个点遍历整个图的最小花费，然后排序，能取多少取多少。那么难点就是怎么去找最小花费，经过画画图可以发现，如果从一个点遍历所有点，如果再回到原点那么代价就是所有边权的2倍，但是我们可以不需要回到原点，所以我们可以选择一个点停下来，也就是找一条距离起点最远的点，到这里就可以结束了。那么问题就转化为了，找出每个点距离它最远的点的距离。如果直接dfs，n个点，就是n*n的复杂度。那么有一个定理就是，对于图上的点，距离它最远的点就是这个图的直径的两个端点中的其中一个。那么我们把直径找出来，然后用端点去dfs两次找出每个点到这两个端点的距离即可。当然还有另一种做法，就是维护3个数组，对于每个点down1就是距离它下面最远的距离，down2是次远的，up是距离上面最远的。
然后也是类似的，就是那个找出树的直径比较偏定理。

代码：

直径作法
int T,n,m,k;
int maxn;
int va[N];
int dis1[N],dis2[N];vector<PII > e[N];void dfs(int now,int p,int dist[])
{if(dist[maxn]<dist[now]) maxn = now;for(auto t:e[now]){int spot = t.fi,w = t.se;if(spot==p) continue;dist[spot] = dist[now]+w;dfs(spot,now,dist);}
}signed main()
{IOS;cin>>n>>m;int sum = 0;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;e[a].pb({b,c});e[b].pb({a,c});sum += c;}dfs(1,0,dis1); //从1找到距离它最远的点maxn for(int i=0;i<=n;i++) dis1[i] = 0;dfs(maxn,0,dis1); //从maxn点开始找出距离它最远的点maxn，同时维护了每个点到它的距离dfs(maxn,0,dis2); //再从manx这个端点遍历他到每个点的距离vector<int > v;for(int i=1;i<=n;i++) v.pb(2*sum-max(dis1[i],dis2[i]));int ans = 0;sort(v.begin(),v.end());for(int i=0;i<v.size();i++){if(m<v[i]) break;m -= v[i];ans++;}cout<<ans;return 0;
}
直接维护上下最远权值做法
int T,n,m,k;
int va[N];
int down1[N],down2[N],up[N];
int ne[N];vector<PII > e[N];void dfs1(int now,int p)
{for(auto t:e[now]){int spot = t.fi,w = t.se;if(spot==p) continue;dfs1(spot,now);if(down1[spot]+w>down1[now]){down2[now] = down1[now];down1[now] = down1[spot]+w;ne[now] = spot; //now的向下最远点是从哪个点过来的}else down2[now] = max(down2[now],down1[spot]+w); }
}void dfs2(int now,int p)
{for(auto t:e[now]){int spot = t.fi,w = t.se;if(spot==p) continue;if(ne[now]==spot) up[spot] = max(up[now]+w,down2[now]+w); //如果从这里过来的话那只能用down2了else up[spot] = max(up[now]+w,down1[now]+w);dfs2(spot,now);}
}signed main()
{IOS;cin>>n>>m;int sum = 0;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;e[a].pb({b,c});e[b].pb({a,c});sum += c;}dfs1(1,0);dfs2(1,0);vector<int > v;for(int i=1;i<=n;i++) v.pb(2*sum-max(up[i],down1[i]));sort(v.begin(),v.end());int ans = 0;for(int i=0;i<v.size();i++){if(m<v[i]) break;m -= v[i];ans++;}cout<<ans;return 0;
}

总结：
多多思考，总结经验。