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

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=510,maxm=50010;
const long double eps=0.00000001,inf=1e8;
int n,m,c[maxn],cnt=0,h[maxn],tot=1,s,t,d[maxn];
long double w[maxm],su[maxn];
pair<int,int> p[maxm];
struct edge{
    int to,next;
    long double c;
}e[maxm<<3];
queue<int> q;
void add(int x,int y,long double w)
{
    tot++;
	e[tot]={y,h[x],w};
    h[x]=tot;
    tot++;
	e[tot]={x,h[y],0};
    h[y]=tot;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	while(q.size()) q.pop();
	q.push(s);
    d[s]=1;
	while(q.size())
    {
		int u=q.front();
        q.pop();
		for(int i=h[u];i;i=e[i].next)
        {
			int y=e[i].to;
            long double c=e[i].c;
			if(d[y]||fabs(c)<eps) continue;
			d[y]=d[u]+1;
            q.push(y);
			if(y==t) return 1;
		}
	}
    return 0;
}
long double dinic(int u,long double flow)
{
	if(u==t||fabs(flow)<eps) return flow;
	long double rest=flow;
	for(int i=h[u];i;i=e[i].next)
    {
		int y=e[i].to;
        long double c=e[i].c;
		if(d[y]!=d[u]+1||fabs(c)<eps) continue;
		long double x=dinic(y,min(rest,c));
		if(fabs(x)<eps)
        {
            d[y]=0;
            continue;
        }
		e[i].c-=x;
        e[i^1].c+=x;
		rest-=x;
		if(fabs(rest)<eps) break;
	}
	return flow-rest;
}
bool check(long double mid)
{
	memset(h,0,sizeof(h));
    tot=1;
	s=n+1;
    t=n+2;
	for(int i=1;i<=n;i++)
	{
        add(s,i,0.5*su[i]);
        add(i,t,mid*c[i]);
    }
	for(int i=1;i<=m;i++)
    {
        add(p[i].first,p[i].second,0.5*w[i]);
        add(p[i].second,p[i].first,0.5*w[i]);
    }
	long double ans=0,flow;
	while(bfs())
    {
        while(flow=dinic(s,1e8))
        {
            ans+=flow;
        }
    }
	return ans+eps<cnt;
}
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%Lf",&p[i].first,&p[i].second,&w[i]);
		su[p[i].first]+=w[i];
        su[p[i].second]+=w[i];
		cnt+=w[i];
	}
	long double l=0,r=500010;
	while(fabs(r-l)>eps)
    {
		long double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.8Lf",l);
	return 0;
}