Description JSOI信息學代表隊一共有N名候選人，這些候選人從1到N編號。方便起見，JYY的編號是0號。每個候選人都由一位 編號比他小的候選人Ri推薦。如果Ri=0則說明這個候選人是JYY自己看上的。為了保證團隊的和諧，JYY需要保證， 如果招募了候選人i，那麼候選人Ri"也一定需要在團 ...
Submit: 844 Solved: 318
[Submit][Status][Discuss]
Description
JSOI信息學代表隊一共有N名候選人，這些候選人從1到N編號。方便起見，JYY的編號是0號。每個候選人都由一位 編號比他小的候選人Ri推薦。如果Ri=0則說明這個候選人是JYY自己看上的。為了保證團隊的和諧，JYY需要保證， 如果招募了候選人i，那麼候選人Ri"也一定需要在團隊中。當然了，JYY自己總是在團隊里的。每一個候選人都有 一個戰鬥值Pi"，也有一個招募費用Si"。JYY希望招募K個候選人（JYY自己不算），組成一個性價比最高的團隊。 也就是，這K個被JYY選擇的候選人的總戰鬥值與總招募總費用的比值最大。
Input
輸入一行包含兩個正整數K和N。 接下來N行，其中第i行包含3個整數Si,Pi,Ri表示候選人i的招募費用，戰鬥值和推薦人編號。 對於100%的數據滿足1≤K≤N≤2500,0<"Si,Pi"≤10^4,0≤Ri<i
Output
輸出一行一個實數，表示最佳比值。答案保留三位小數。
Sample Input
1 21000 1 0
1 1000 1
Sample Output
0.001HINT
2017.9.12新加數據一組 By GXZlegend
Source
應該是比較裸的題目 01分數規劃+樹形依賴背包。 01分數規劃的話按照套路二分檢驗，註意設置好精度 樹形依賴背包註意在枚舉的時候上限應該在枚舉之後更改否則會被卡成$O(N^3\log ans)$
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1e6+10,INF=1e4+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();} return x*f; } int N,K; int S[MAXN],P[MAXN],R[MAXN]; struct node { int u,v,nxt; }edge[MAXN]; int head[MAXN]; int num=1; inline void AddEdge(int x,int y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } double dp[2501][2501],/*i處，選了j個*/siz[MAXN],w[MAXN]; void find(int now) { siz[now]=1; for(int i=head[now];i!=-1;i=edge[i].nxt) find(edge[i].v),siz[now]+=siz[edge[i].v]; } void dfs(int now) { int tot=0,b=0; if(now) dp[now][1]=w[now],tot=1,b++; else dp[now][0]=0; for(int i=head[now];i!=-1;i=edge[i].nxt) { dfs(edge[i].v); for(int j=tot;j>=b;j--)//背包容量 for(int k=1;k<=siz[edge[i].v];k++) dp[now][j+k]=max(dp[now][j+k],dp[now][j]+dp[edge[i].v][k]); tot+=siz[edge[i].v];//必須在後面加 } } bool check(double val) { memset(dp,0xc2,sizeof(dp)); for(int i=1;i<=N;i++) w[i]=P[i]-val*S[i]; dfs(0); return dp[0][K]>=0; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); K=read(),N=read(); for(int i=1;i<=N;i++) { S[i]=read(),P[i]=read(),R[i]=read(); AddEdge(R[i],i); } find(0); double l=0,r=INF; double ans=0; while(r-l>1e-5) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.3lf",(l+r)/2); return 0; }
