# Tomoya【省选模拟赛】

## 果然大多数乱搞题都和二分有关

Posted by yjjr's blog on March 5, 2018

n,m<=1000

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e16
#define eps 1e-12
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
struct edge{int to,next;double z;}e[maxn<<1];
struct Q{double z;int x;};
inline bool operator > (Q a,Q b){return a.z>b.z;}
double b[maxn],c[maxn],f[maxn],l,r,mid;
int last[maxn],id[maxn],n,m,S,T,cnt,cnt1,cnt2;
bool p[maxn],P[maxn];
priority_queue <Q,vector <Q> ,greater <Q> > que;
inline double doit(){
while(!que.empty())que.pop();
cnt=cnt1;
rep(i,0,cnt-1)que.push((Q){b[i]+c[0],i}),id[i]=cnt;
double re=0,p=1;
while(!que.empty()&&p>eps){
Q now=que.top();
int x=now.x;
double P=p*(id[x]-x-1)/(id[x]-x);
id[x]--;re+=(p-P)*now.z;p=P;que.pop();
if(id[x]>x)que.push((Q){b[x]+c[cnt-id[x]],x});else break;
}
return re;
}
void dfs(int x){
p[x]=1;
if(x==T){P[x]=1;return;}
reg(x){
if(!p[e[i].to])dfs(e[i].to);
P[x]|=P[e[i].to];
}
if(!P[x]){f[x]=inf;return;}
cnt1=cnt2=0;l=0,r=1e5;
reg(x)b[cnt1++]=e[i].z;
sort(b,b+cnt1);
rep(num,1,40){
mid=(l+r)/2,cnt2=0;
reg(x)c[cnt2++]=((e[i].to==x)?mid:f[e[i].to]);
sort(c,c+cnt2);
if(mid<doit())l=mid;else r=mid;
}
f[x]=l;
}
int main()
{