python的网站开发,电商培训方案,做网站公司销售开场白,深圳罗湖企业网站建设P5021 [NOIP 2018 提高组] 赛道修建
题意简述
给定一棵含 n n n 个点的无向带权树#xff0c;求将其分裂为 m m m 条链后#xff0c;最短的一条链的最大长度是多少#xff1f;
点可以重复使用#xff0c;边不可以重复使用。
思路
二分答案贪心判定貌似可以#xff…P5021 [NOIP 2018 提高组] 赛道修建
题意简述
给定一棵含 n n n 个点的无向带权树求将其分裂为 m m m 条链后最短的一条链的最大长度是多少
点可以重复使用边不可以重复使用。
思路
二分答案贪心判定貌似可以
看一下数据规模。 a i 1 a_i 1 ai1 菊花图。链最多含两条边。 b i a i 1 b_i a_i 1 biai1 整棵树是一条链。
分支不超过 3 3 3 感觉在有意引导。是二叉树。
菊花图是最有用的考虑菊花图时如何求解。设当前二分出的赛道长度为 m i d mid mid
显然此时一条链最多含两条边考虑按边权排序
1**.已经大于 m i d mid mid 的边**不必再拼接其他边因为它已经能产生贡献了再与其他边拼接自身贡献不变的同时阻止了其他边产生贡献的可能必然不优。
2.剩下的边里从小到大对于每个边 x x x 二分减小查询复杂度查询出与它拼接能产生长度大于 m i d mid mid 的最短的一条边即找到最小的 y y y 满足 x y ≥ m i d x y \ge mid xy≥mid 。
为什么如果用更长的边 y y y 那么可能会使得原本可以产生贡献的 y y y 被抛弃又因为自身不够长而无法再次与别的边产生贡献相反被使用的更长边显然更有可能与别的边拼接产生贡献因此选择最小的 y y y 即可。
菊花图的情况已经可以求解。不妨把每一个子树视作上述菊花图的情况现在子树内已经得到最优解如何向父节点扩展
由于每个结点到父节点的边是唯一的那么只能选择一条边传递给父节点供后续产生贡献那么不难想到传递 剩余未匹配边 中最长的一条。因为最长后续产生贡献的概率越大缓解了父节点的匹配压力保证了全局最优解。可以用 d p [ u ] dp[u] dp[u] 表示当前结点最长未匹配边到父节点出只需将父节点的边权加上 d p [ u ] dp[u] dp[u] 即可。
当子树求解完成时与子节点相连的边指向哪里已经不再重要只需记录并排序边权即可用 m u l t i s e t multiset multiset 。
代码实现
其实细节很多
1.C11 及以上 erase 返回删除指定元素后下一个有效迭代器。
2.在 m u l t i s e t multiset multiset 中查找到第一个大于等于 y y y 的元素时一定要判断有可能就是自己如果未判断就删除会引起各种奇怪错误。
我因为 r e s m res m resm 放在 d f s dfs dfs 后调了半天全输出 0 0 0。
#include bits/stdc.husing namespace std;const int N 5e4 100;
int n,m,L INT_MAX,R,res,ans;
bool vis[N];
struct Edges{int v,w;
};
vector Edges gra[N];void read(int res){int x 0,w 1;char ch 0;while(ch 0 || ch 9){if(ch -) w -1;ch getchar();}while(ch 0 ch 9){x (x 3) (x 1) (ch - 0);ch getchar();}res x * w;
}bool cmp(Edges a,Edges b){return a.w b.w;
}int dfs(int u,int limit){vis[u] true;//记录与子树相连的边 int cnt 0;multiset int match;//优先在子树内求解for(auto edge : gra[u]){int v edge.v;//连接父亲的边跳过 if(vis[v]) continue;match.insert(edge.w dfs(v,limit));} //在当前子树匹配//长度已经满足的 for(auto it match.begin();it ! match.end();)if(*it limit){it match.erase(it);res--; }else{it;}
// 需要两两匹配的for(auto it match.begin();it ! match.end();){int y limit - (*it);auto _it match.lower_bound(y);if(_it match.end() || _it it){it;continue; } res--;match.erase(_it);it match.erase(it);} if(match.empty()) return 0;return *match.rbegin();
}void solve(){int l L,r R,mid;while(l r){mid l r 1;memset(vis,false,sizeof(vis));res m;dfs(1,mid);if(res 0){l mid 1;ans mid;}else r mid - 1; }printf(%d\n,ans);
} int main(){read(n);read(m);int u,v,w;for(int i 1;i n;i){read(u);read(v);read(w);gra[u].push_back({v,w});gra[v].push_back({u,w});L min(L,w);R w;}//二分答案solve(); return 0;
}挺好的一道树上二分贪心。
