记录编号	590628	评测结果	AAAAAAAAAA
题目名称	制作人偶	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.276 s
提交时间	2024-07-10 16:12:58	内存使用	6.17 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define db double
#define F(i,a,b) for(int i = a;i <= b;i++)
#define D(i,a,b) for(int i = a;i >= b;i--)
const int N = 2e5,M = 5e5+10;
const double eps = 1e-9,inf = 1e8;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int n,m,s,t;
struct made{
    int ver,nx;db ed;
};
struct flow{
    made e[M<<1];
    int hd[N],tot = 1;
    void add(int x,int y,db z){
        e[++tot] = {y,hd[x],z},hd[x] = tot;
        e[++tot] = {x,hd[y],0},hd[y] = tot;
    }
    int d[N],cur[N];
    db dinic(int x,db fl){
        if(x == t)return fl;
        db rest = fl;
        for(int i = cur[x];i && fabs(rest) > eps;i = e[i].nx){
            int y = e[i].ver;cur[x] = i;// 
            if(fabs(e[i].ed) > eps && d[y] == d[x] + 1){
                db c = dinic(y,min(rest,e[i].ed));
                if(fabs(c) < eps)d[y] = 0;
                e[i].ed -= c,e[i^1].ed += c;
                rest -= c;
            }
        }
        return fl - rest;
    }
    db bfs(){
        db ans = 0;
        while(1){
            memset(d,0,sizeof d);
            memcpy(cur,hd,sizeof hd);
            queue<int>q;
            q.push(s);q.push(s),d[s] = 1;
            while(!q.empty()){
                int x = q.front();q.pop();
                for(int i = hd[x];i;i = e[i].nx){
                    int y = e[i].ver;
                    if(fabs(e[i].ed) > eps && !d[y])d[y] = d[x] + 1,q.push(y);
                }
            }//分层图 
            if(!d[t])return ans;
            ans += dinic(s,inf);//多路增广 
        }
    }
}f;


db w[N],sum,z[N];
struct node{
    int x,y; db v;
}a[N];
bool check(double mid){
    f.tot = 1;
    memset(f.hd,0,sizeof f.hd);
//    for(int i = 1;i <= 2*n;i++)f.hd[i] = 0;
    for(int i = 1;i <= n;i++){
        f.add(i,t,mid * w[i]);
        f.add(s,i,z[i]);
    }
    for(int i = 1;i <= m;i++){
        f.add(a[i].x,a[i].y,a[i].v / 2.0);
        f.add(a[i].y,a[i].x,a[i].v / 2.0);
    }
    db s = f.bfs();
    return sum - s > eps;
}
int main(){
    freopen("asiram.in","r",stdin);
    freopen("asiram.out","w",stdout);
    n = read(),m = read();
    s = n+1,t = n+2;
    for(int i = 1;i <= n;i++)w[i] = read();
    for(int i = 1;i <= m;i++){
        a[i].x = read(),a[i].y = read(),a[i].v = read();
        z[a[i].x] += a[i].v / 2.0,z[a[i].y] += a[i].v / 2.0;;
        sum += a[i].v;
    }
    //
    double l = 0,r = 1e5;
    while(l + eps < r){
        double mid = (l + r) / 2;
        if(check(mid))l = mid;
        else r = mid;
    }
    printf("%lf\n",l + eps);


    return cerr<<endl<<"Time:"<<clock()<<"ms"<<endl,0;
     
}