Tomoya【省选模拟赛】

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


本文总阅读量
Posted by yjjr's blog on March 5, 2018

标签:二分

题目

这里写图片描述

n,m<=1000

分析

主要问题在于存在自环,每次可以重复绕自己

把每个点的出边从小到大排序

同时把另一端端点到终点的距离从小到大排序

计算的是n * m种配对中最小的和的期望

可以枚举每个和

将所有大于等于它的概率统计进入答案,概率扫描的时候需要用优先队列简单维护

但我们不确定距离x,所以需要二分这个参数

对每个点求一遍就可以得到答案

\[时间复杂度O(n * m\log ANS)\]

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;
inline ll read()
{
	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()
{
	n=read(),m=read(),S=read(),T=read();
	rep(i,1,m){
		int u=read(),v=read();
		scanf("%lf",&e[i].z);
		e[i].to=v,e[i].next=last[u],last[u]=i;
	}
	dfs(S);
	printf("%.8lf\n",f[S]);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr