Acwing 361.观光奶牛
题意
给定一张 L个点、P条边的有向图，每个点都有一个权值f[i]，每条边都有一个权值t[i]。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
注意：数据保证至少存在一个环。
思路
代码
// Author：zzqwtcc // Problem: 观光奶牛 // Contest: AcWing // Time：2021-10-24 21:51:14 // URL: https://www.acwing.com/problem/content/363/ // Memory Limit: 64 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) // #define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;} template<typename T>void debug(T t){cerr << t << endl;} template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;} template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;} // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e3 + 10;; int n, m; int f[N]; vector<PII>vec[N]; bool st[N]; int d[N]; int cnt[N]; bool spfa(double mid){ memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int>q; rep(i,1,n)q.push(i),st[i] = true; while(q.size()){ int u = q.front(); q.pop(); st[u] = false; for(int i = 0 ;i < vec[u].size();++i){ int j = vec[u][i].second; int dis = vec[u][i].first; if(d[j] < d[u] + f[u] - mid * dis){ d[j] = d[u] + f[u] - mid * dis; cnt[j] = cnt[u] + 1; if(cnt[j] >= n)return true; if(!st[j]){ st[j] = true; q.push(j); } } } } return false; } void solve() { cin >> n >> m; rep(i,1,n)scanf("%d",&f[i]); while(m--){ int u,v,w;scanf("%d%d%d",&u,&v,&w); vec[u].push_back({w,v}); } double l = 0.0,r = 1010.0; while(r - l > 1e-4){ double mid = (l + r ) / 2; if(spfa(mid))l = mid; else r = mid; } printf("%.2lf\n",r); } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
