沒有證明的貪心就是亂搞

解析

把標(biāo)簽寫在題面上的一道題…
顯然要二分答案然后看能不能分出來m個

關(guān)鍵策略是每個結(jié)點內(nèi)部盡可能的多匹配的前提下，給父親傳一個最大的
這不紀(jì)念品分組？
然后我就無腦的敲了個雙指針的貪心上去
然后就WA掉了qwq
（由于帶限制的點太多這竟然還有80）
紀(jì)念品分組的貪心只保證了盡可能多匹配
卻不能保證剩下一個最大的
一個簡單的例子是較小值和次大值匹配，把最大值傳上去
然而如果按照從小往大掃，每一個貪心的想與盡可能小的匹配，這樣就能保證貪心的正確性了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=50050; const int mod=998244353; inline ll read() {ll x=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; struct node{int to,nxt,w; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],w};fi[x]=cnt;return; } int len[N],tot,now,ans; vector<int>v[N]; bool ok[N]; void dfs(int x,int f){v[x].clear();for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dfs(to,x);if(len[to]+p[i].w>=now) ans++;else v[x].push_back(len[to]+p[i].w);}sort(v[x].begin(),v[x].end());int l=0,r=v[x].size()-1;for(int i=0;i<=r;i++) ok[i]=1;for(int i=0;i<=r;i++){if(!ok[i]) continue;int st=0,ed=r+1;while(st<ed){int mid=(st+ed)>>1;if(v[x][mid]+v[x][i]>=now) ed=mid;else st=mid+1;}while(st<=r&&(!ok[st]||st==i)) st++;if(st<=r){ok[st]=ok[i]=0;//printf("x=%d %d %d\n",x)ans++;}}len[x]=0;for(int i=v[x].size()-1;i>=0;i--){if(ok[i]){len[x]=v[x][i];break;}}return; } bool check(int k){ans=0;now=k;dfs(1,0);return ans>=m; } signed main() {#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();for(int i=1;i<n;i++){int x=read(),y=read(),w=read();addline(x,y,w);addline(y,x,w);tot+=w;} // printf("%d\n",check(38));int st=0,ed=tot;while(st<ed){int mid=(st+ed+1)>>1;if(check(mid)) st=mid;else ed=mid-1;}printf("%d\n",st);return 0; }

總結(jié)

以上是生活随笔為你收集整理的NOIP2018洛谷P5021：修建赛道的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。