记录编号	590646	评测结果	AAAAAAAAAA
题目名称	制作人偶	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	0.888 s
提交时间	2024-07-10 16:33:18	内存使用	16.52 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 505, M = 5005, S = 501, T = 502;
const double eps = 1e-8;
int n, m, a[M], b[M], d[N], now[N];
double c[M], sum, w[N];
vector<pair<int, double> > v[N];
vector<int> belong[N];
bool bfs(){
    memset(d, 0x3f, sizeof(d));
    memset(now, 0, sizeof(now));
    d[S] = 0;
    queue<int> q;
    q.push(S);
    int e = 0;
    while(q.size()){
        int x = q.front();
        q.pop();
        if(x == T){
            e = 1;
        }
        for(auto t : v[x]){
            int y = t.fi;
            if(d[y] > d[x] + 1 && t.se >= eps){
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
    return e;
}
double dfs(int x, double flow){
    if(x == T){
        return flow;
    }
    double used = 0;
    for(int i = now[x]; i < v[x].size(); i ++){
        now[x] = i;
        int y = v[x][i].fi;
        if(v[x][i].se >= eps && d[y] == d[x] + 1){
            double vlow = dfs(y, min(flow - used, v[x][i].se));
            if(vlow >= eps){
                used += vlow;
                v[x][i].se -= vlow;
                v[y][belong[x][i]].se += vlow;
                if(flow - used <= eps){
                    break;
                }
            }
        }
    }
    return used;
}
void add(int x, int y, double w){
    belong[x].push_back(v[y].size());
    belong[y].push_back(v[x].size());
    v[x].push_back(mp(y, w));
    v[y].push_back(mp(x, 0.0));
    return;
}
bool check(double mid){
    for(int i = 1; i <= n; i ++){
        v[i].clear();
    }
    v[S].clear(), v[T].clear();
    for(int i = 1; i <= m; i ++){
        add(S, a[i], c[i] / 2.0);
        add(S, b[i], c[i] / 2.0);
        add(a[i], b[i], c[i] / 2.0);
        add(b[i], a[i], c[i] / 2.0);
    }
    for(int i = 1; i <= n; i ++){
        add(i, T, mid * w[i]);
    }
    double ans = 0;
    while(bfs()){
        ans += dfs(S, 1e9);
    }
    // cout << "***" << mid << " " << sum << " " << ans << "\n";
    return sum - ans >= eps;
}
signed main(){
    freopen("asiram.in", "r", stdin);
    freopen("asiram.out", "w", stdout);
    n = mread(), m = mread();
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
    }
    for(int i = 1; i <= m; i ++){
        a[i] = mread(), b[i] = mread();
        cin >> c[i];
        sum += c[i];
    }
    double l = eps, r = 1e6;
    while(r - l > eps){
        double mid = (l + r) / 2.0;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    printf("%.7lf", l);
    return 0;
}