免费网站建设翻译,品牌平价网站建设,南充建设网站,wordpress调用幻灯片正题
题目链接:https://www.luogu.org/problemnew/show/P5021 题目大意
一棵树找mmm条不重边路径使得最短的那条最长。 解题思路
首先最小的最大显然二分一下答案。之后问题转换为找最多条长度不小于midmidmid的路径。
如果dpdpdp的话需要二维#xff0c;显然不能胜任本题…正题
题目链接:https://www.luogu.org/problemnew/show/P5021 题目大意
一棵树找mmm条不重边路径使得最短的那条最长。 解题思路
首先最小的最大显然二分一下答案。之后问题转换为找最多条长度不小于midmidmid的路径。
如果dpdpdp的话需要二维显然不能胜任本题。
那我们考虑贪心一旦有长度不小于kkk的我们马上统计入答案这样就可以节省掉dpdpdp的一维。现在我们的问题就是在一个交界点时对于每条子节点的路径要么直接结束那条路径要么往上连接要么子节点之间连接。
那我们考虑如果一条传上来的路径长度valival_ivali
若vali≥midval_i\geq midvali≥mid那么直接结束改路径。 若valilt;midval_ilt;midvalimid那么优先考虑连接子节点因为往上传只能传一条所以最大贡献为111但是子节点之间连接的话贡献也为111。
那我们开一个平衡树或multisetmultisetmultiset(我是用multisetmultisetmultiset)储存所有valilt;midval_ilt;midvalimid的值。每次取出最小的valminval_{min}valmin并在剩下的中寻找一个valk≥mid−valminval_k\geq mid-val_{min}valk≥mid−valmin中最小的一个于其匹配。
然后在找没有匹配中最大的那个向上传就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includeset
using namespace std;
const int N50100;
struct node{int to,next,w;
}a[N*2];
multisetint s[N];
multisetint::iterator it;
int n,m,tot,ans,k,l,r,sum;
int ls[N];
void addl(int x,int y,int z)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].wz;
}
int dfs(int x,int fa)
{for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;int valdfs(y,x)a[i].w;if(valk) ans;else s[x].insert(val);}int up0;while(!s[x].empty()){int val*s[x].begin();if(s[x].size()1){s[x].erase(s[x].find(val));return max(up,val);}its[x].lower_bound(k-val);if(its[x].end()) upmax(up,val);else{if(its[x].begin()s[x].count(*it)1) it;ans;s[x].erase(s[x].find(*it));}s[x].erase(s[x].find(val));}return up;
}
bool check(int x)
{kx;ans0;dfs(1,1);if(ansm) return true;return false;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y,z;scanf(%d%d%d,x,y,z);addl(x,y,z);addl(y,x,z);sumz;}l0;rsum/m1;while(lr){int mid(lr)/2;if(check(mid)) lmid1;else rmid-1;}printf(%d,r);
}
