https://vjudge.net/problem/HDU-6769

題目大意：給你n個點，有n-1條邊，每條邊有a，b兩個權(quán)值，給你一個k，恰好有k條邊的權(quán)值取a，其余取b的時候，樹的直徑的最小值。

思路：答案具有單調(diào)性直接二分直徑（在比賽的時候我壓根想不到），然后用這個直徑對樹形dp做一個限制，如果鏈權(quán)值相加大于mid的時候則不轉(zhuǎn)移狀態(tài)。dp【i】【j】代表i的子樹中選擇了j條邊取a權(quán)值的情況下，從i出發(fā)能達到最遠就距離。（類似樹上背包吧）

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define pb push_back #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=998244353; const ll N =5e5+10; const ll M =250000; const double eps = 1e-4; //const double pi=acos(-1); ll re(){ll x;scanf("%lld",&x);return x; } int n,k; struct p{int to,nex;pii w; }e[N]; int h[N]; ll dp[20010][21],temp[100]; int siz[20010]; int idx; void add(int u,int v,ll a,ll b){e[idx]={v,h[u],{a,b}};h[u]=idx++; } void dfs(int u,int fa,ll mid){siz[u]=dp[u][0]=0;for(int i=h[u];~i;i=e[i].nex){int v=e[i].to;if(v==fa) continue;dfs(v,u,mid);int num=min(siz[u]+siz[v]+1,k);for(int j=0;j<=num;j++) temp[j]=mid+1;for(int j=0;j<=min(siz[u],num);j++){for(int p=0;p<=min(siz[v],num)&&j+p<=num;p++){if(p+j+1<=num&&dp[u][j]+dp[v][p]+e[i].w.fi<=mid)temp[j+p+1]=min(temp[j+p+1],max(dp[u][j],dp[v][p]+e[i].w.fi));if(dp[u][j]+dp[v][p]+e[i].w.sc<=mid)temp[j+p]=min(temp[j+p],max(dp[u][j],dp[v][p]+e[i].w.sc));}}siz[u]+=siz[v]+1;for(int j=0;j<=num;j++) dp[u][j]=temp[j];}} void slove(){n=re(),k=re();for(int i=1;i<=n;i++) h[i]=-1;idx=0;ll l=0,r=0;for(int i=1;i<n;i++){ll u=re(),v=re(),a=re(),b=re();add(u,v,a,b);add(v,u,a,b);r+=max(a,b);}ll ans=0;while(l<=r){ll mid=(l+r)/2;dfs(1,0,mid);if(dp[1][k]<=mid){ans=mid;r=mid-1;}else l=mid+1;}cout<<ans<<endl; }int main(){int t;t=re();while(t--) slove();return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 6769-In Search of Gold-二分+树形dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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