Noip2018Day1T3 赛道修建
程序员文章站
2022-07-05 17:34:53
"题目链接" problem 给出一棵有边权的树。一条链的权值定义为该链所经过的边的边权值和。需要选出$m$条链,求$m$条链中权值最小的链的权值最大是多少。 solution 首先显然二分。 然后考虑如何判断二分出来的一个答案$x$是否是可行的。也就是能否选出$m$条链,每条链权值都大于等于$x$ ......
problem
给出一棵有边权的树。一条链的权值定义为该链所经过的边的边权值和。需要选出\(m\)条链,求\(m\)条链中权值最小的链的权值最大是多少。
solution
首先显然二分。
然后考虑如何判断二分出来的一个答案\(x\)是否是可行的。也就是能否选出\(m\)条链,每条链权值都大于等于\(x\)。这个其实是贪心。
定义直链为从一个某个点的祖先到该点的路径。
可以发现每条链要么就是一条直链,要么由两条直链在某个点处合并起来得到。
贪心的地方在于,对于每个点肯定都是优先将能合成的直链合成。然后再保证向上传递的直链长度最大。因为即便向上传递的长度特别大,产生的贡献也做多只能是\(1\)。所以要先保证在当前子树上合成最多的链。
然后问题就变成了在一棵子树内得到一些直链长度。现在把这些直链两两合并成权值大于等于\(x\)的链。然后保证剩下的直链长度最大。
这里可以二分答案一下。也可以用个\(multiset\)处理。反正是很可做的一个问题。
代码中有各档部分分,bf5为正解
code
#include<set> #include<cstdio> #include<iostream> #include<cstdlib> #include<ctime> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef long long ll; const int n = 100010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int n,m; struct node { int v,nxt,w; }e[n << 1]; int head[n],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; } namespace bf1 { int dis[n]; void dfs(int u,int fa) { for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; dis[v] = dis[u] + e[i].w; dfs(v,u); } } void main() { dfs(1,0); int x = 0; for(int i = 1;i <= n;++i) if(dis[i] > dis[x]) x = i; // cout<<x<<endl; memset(dis,0,sizeof(dis)); dfs(x,0); int ans = 0; for(int i = 1;i <= n;++i) ans = max(ans,dis[i]); cout<<ans; } } namespace bf2 { int a[n],cnt; int check(int x) { int p = 1,ret = 0; for(int i = cnt;i > p;--i) { if(a[i] > x && i > p) {ret++;continue;} while(a[p] + a[i] < x && p < i) ++p; if(p < i) ret++,p++; else break; } return ret; } void main() { int l = 100000,r = 0; for(int i = 1;i <= ejs;i += 2) a[++cnt] = e[i].w,l = min(l,a[cnt]),r += a[cnt]; sort(a + 1,a + cnt + 1); int ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(check(mid) >= m) ans = mid,l = mid + 1; else r = mid - 1; } cout<<ans<<endl; } } int du[n]; namespace bf3 { int a[n],cnt; void dfs(int u,int fa) { for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; a[++cnt] = e[i].w; dfs(v,u); } } int check(int x) { int now = 0,ret = 0; for(int i = 1;i <= cnt;++i) { now += a[i]; if(now >= x) now = 0,ret ++; } return ret; } void main() { for(int i = 1;i <= n;++i) if(du[i] == 1) {dfs(i,0);break;} int l = 1000000,r = 0; for(int i = 1;i <= ejs;i += 2) { l = min(l,e[i].w);r += e[i].w; } int ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(check(mid) >= m) ans = mid,l = mid + 1; else r = mid - 1; } cout<<ans<<endl; } } int l = 100000,r; namespace bf5 { int ans; int dfs(int u,int fa,int x) { multiset<int>s; int ret = 0; // if(!s.empty()) printf("%d\n",u); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; int k = dfs(v,u,x); if(k + e[i].w >= x) ans++; else s.insert(k + e[i].w); } while(!s.empty()) { multiset<int>::iterator it = s.begin(); int k = *it; s.erase(it); multiset<int>::iterator is = s.lower_bound(x - k); if(is == s.end()) ret = max(ret,k); else ans++,s.erase(is); } // s.clear(); // printf("%d %d\n",u,ret); return ret; } void main() { int l = l,r = r,ans = 0; while(l <= r) { int mid =(l + r) >> 1; ans = 0;dfs(1,0,mid); if(ans >= m) ans = mid,l = mid + 1; else r = mid - 1; } cout<<ans; } } int main() { n = read(),m = read(); int bz1 = 1,bz2 = 1; for(int i = 1;i < n;++i) { int u = read(),v = read(),w = read(); l = min(l,w);r += w; du[u]++;du[v]++; add(u,v,w);add(v,u,w); if(u != 1) bz1 = 0; if(v != u + 1) bz2 = 0; } if(m == 1) {bf1::main();return 0;} if(bz1) {bf2::main();return 0;} if(bz2) {bf3::main();return 0;} bf5::main(); return 0; } /* 7 1 1 2 10 1 3 5 2 4 9 2 5 8 3 6 6 3 7 7 */
上一篇: 一组绕口令,练练你的嘴皮子
下一篇: 显微镜下的webpack4入门