bzoj4753[JSOI2016]最佳團體
題意:01分數規劃,但可選的數字之間存在森林形的依賴關系(可以認為0號點是個虛根,因為并不能選).
雖然有森林形的依賴關系，但還是可以套分數規劃的思路,二分答案k,判斷是否存在一個比值大于k的方案
即是否存在一種選取方式使得sigma{fight[i],i is choosed}/sigma{cost[i],i is choosed}>=k
移項,發現只需要sigma{fight[i]-cost[i]*k,i is choosed}>=0,也就是把每個點的權值設置成”戰斗力-花費*比值”,判斷是否存在一種滿足依賴關系的選取方案使得選擇的權值之和>=0,那么讓權值之和盡量大判定最大值是否大于等于0即可.定義f[i][j]表示i為根的子樹中選取j個點時的最大權值,用背包暴力轉移,看似是O(n^3)的,但仔細分析發現復雜度是O(n^2)的,因為每次合并一棵子樹時付出的代價是”已經合并的兄弟子樹的大小之和”*”正在合并的這棵子樹的大小”,實質上是樹上每對節點在LCA處貢獻時間復雜度,這一部分相當于bzoj4033.
于是總體復雜度是O (log(ans)*N^2),n是2500,感覺很虛但是能跑過去…注意處理某棵子樹如果選擇那么子樹的根節點必須選擇,以及0號節點的處理.再有就是二分精度一定要調好.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2505; struct edge{ int to,next; }lst[maxn];int first[maxn],len=1; void addedge(int a,int b){ lst[len].to=b;lst[len].next=first[a];first[a]=len++; } int k,n; int cost[maxn],fight[maxn],prt[maxn],sz[maxn]; double w[maxn]; double f[maxn][maxn]; void dfs(int x){ sz[x]=1; for(int pt=first[x];pt;pt=lst[pt].next){ dfs(lst[pt].to); sz[x]+=sz[lst[pt].to]; } } void dp(int x){ int tot=0; if(x)f[x][1]=w[x],tot=1; else f[x][0]=0; for(int pt=first[x];pt;pt=lst[pt].next){ dp(lst[pt].to);tot+=sz[lst[pt].to]; for(int i=tot;i>=0;--i){ for(int j=0;j<=sz[lst[pt].to]&&j<=i;++j){ f[x][i]=max(f[x][i],f[x][i-j]+f[lst[pt].to][j]); } } } } bool check(double ans){ for(int i=1;i<=n;++i){ w[i]=fight[i]-ans*cost[i]; } memset(f,0xc2,sizeof(f)); dp(0);//printf("%.3f\n",f[2][1]); return f[0][k]>=0; } int main(){ scanf("%d%d",&k,&n); for(int i=1;i<=n;++i){ scanf("%d%d%d",&cost[i],&fight[i],&prt[i]);addedge(prt[i],i); } dfs(0); double l=0,r=1e4; while(r-l>1e-5){ double mid=(l+r)/2; if(check(mid))l=mid; else r=mid; } printf("%.3f\n",(r+l)/2); return 0; }
浙公網安備 33010602011771號