记录编号	590589	评测结果	AAAAAAAAAA
题目名称	制作人偶	最终得分	100
用户昵称	dbp9	是否通过	通过
代码语言	C++	运行时间	0.593 s
提交时间	2024-07-10 15:41:58	内存使用	4.08 MiB

/*题解来源：@ op_组撒头屯 ，在下只是一个搬运工~~ */ 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int N=500+5;
const int M=5000+5;
const ld eps=1e-8;
int n,m;
int c[N],tot=0;
int w[M],sum[N];
pii p[M];
struct edge{int to,next;ld c;};
edge eg[M*8];int head[N],ne=1;
inline void adde(int x,int y,ld c){
	eg[++ne]={y,head[x],c},head[x]=ne;
	eg[++ne]={x,head[y],0},head[y]=ne;
}
int S,T;
int dep[N];
queue<int>Q;
bool bfs(){
	while(!Q.empty())Q.pop();
	memset(dep,0,sizeof(dep));
	Q.push(S),dep[S]=1;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for (int i=head[u];i;i=eg[i].next){
			int v=eg[i].to;ld c=eg[i].c;
			if (dep[v]||fabs(c)<eps)continue;
			dep[v]=dep[u]+1,Q.push(v);
			if (v==T)return 1;
		}
	}return 0;
}
ld dinic(int u,ld flow){
	if (u==T||fabs(flow)<eps)return flow;
	ld res=flow;
	for (int i=head[u];i;i=eg[i].next){
		int v=eg[i].to;ld c=eg[i].c;
		if (dep[v]!=dep[u]+1||fabs(c)<eps)continue;
		ld cur=dinic(v,min(res,c));
		if(fabs(cur)<eps){dep[v]=0;continue;}
		eg[i].c-=cur,eg[i^1].c+=cur;
		res-=cur;
		if (fabs(res)<eps)break;
	}
	return flow-res;
}
bool check(ld mid){
	memset(head,0,sizeof(head)),ne=1;
	S=n+1,T=n+2;
	for (int i=1;i<=n;i++)adde(S,i,0.5*sum[i]),adde(i,T,mid*c[i]);
	for (int i=1;i<=m;i++)adde(p[i].fi,p[i].se,0.5*w[i]),adde(p[i].se,p[i].fi,0.5*w[i]);
	ld ans=0,flow;
	while(bfs())while(flow=dinic(S,1e8))ans+=flow;
	return ans+eps<tot;
}
int main(){
	freopen ("asiram.in","r",stdin);
	freopen ("asiram.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)scanf("%d",&c[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&p[i].fi,&p[i].se,&w[i]);
		sum[p[i].fi]+=w[i],sum[p[i].se]+=w[i];
		tot+=w[i];
	}
	ld l=0,r=5e5;
	while(fabs(r-l)>eps){
		ld mid=(l+r)/2;
		if (check(mid))l=mid;
		else r=mid;
	}
	printf("%.8Lf\n",l);
	return 0;
}