https://vjudge.net/contest/392376#problem/H
学习自
https://blog.csdn.net/u014609452/article/details/68482711?locationNum=10&fps=1
对时间分治原来可以不用在线段树上搞，直接动态开vector和数组保证只有Logn*m的空间就行了
把边从大到小排序，然后枚举一个边界，当前最大的割边就是edg[l+1].w，然后从1-l大的边都是没有割的，比边界小的[l+2,m]的边都是随便连的，也就是现在剩下一堆由大边连起来的连通块随便组合成两部分，由于要使得答案最小，我们需要较小的那一部分最大。于是就可以用bitset来搞01背包DP，判断较小的那一半部分最大可以是多少。
用并查集维护连通块大小，并判断每一个连通块大小是从哪些时间是存在的，然后就能通过对时间分治，使得01背包dp在分治中从上到下只有增加没有就少，就能得到l==r时每一时间下01背包dp的情况，那么复杂度是O(mlogn * n/W)的
#include<bits/stdc++.h> using namespace std; const int maxn=14010; const int maxm=30010; int n,m; int sz[maxn],f[maxn],clk[maxn]; struct ed { int u,v,w; bool operator <(const ed &b)const { return w>b.w; } }edg[maxm]; struct event { int l,r,w; event(int a=0,int b=0,int c=0) { l=a;r=b;w=c; } }; vector<event> vec; double ans=1e30; bitset<maxn> B; inline int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } inline void prework() { scanf("%d%d",&n,&m); int u,v,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); ++u;++v; edg[i]=ed{u,v,w}; } sort(edg+1,edg+1+m); for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,clk[i]=0; int x,y; for(int i=1;i<=m;i++) { x=find(edg[i].u),y=find(edg[i].v); if(x==y) continue; vec.push_back(event(clk[x],i-1,sz[x])); vec.push_back(event(clk[y],i-1,sz[y])); f[x]=y;sz[y]+=sz[x];clk[y]=i; } for(int i=1;i<=n;i++) if(f[i]==i) vec.push_back(event(clk[i],m,sz[i])); } inline void solv(int l,int r,vector<event> &vec) { bitset<maxn> tmp;tmp=B;int len=vec.size(); if(l==r) { for(int i=0;i<len;i++) if(vec[i].l<=l && r<=vec[i].r) B|=B<<vec[i].w; for(int i=1;i<=n/2;i++) if(B[i]) ans=min(ans,(double)edg[l+1].w/i);; B=tmp; return; } vector<event> v1,v2; int mid=(l+r)>>1; for(int i=0;i<len;i++) if(vec[i].l<=l && r<=vec[i].r) B|=B<<vec[i].w; else { if(vec[i].l<=mid) v1.push_back(vec[i]); if(vec[i].r>mid) v2.push_back(vec[i]); } solv(l,mid,v1); solv(mid+1,r,v2); B=tmp; } inline void mainwork() { B[0]=1; solv(0,m,vec); } inline void print() { printf("%.11f\n",ans); } int main() { prework(); mainwork(); print(); return 0; }
