제출 #540823

#제출 시각아이디문제언어결과실행 시간메모리
540823Lobo여행하는 상인 (APIO17_merchant)C++17
100 / 100
73 ms4424 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 110; const int maxk = 1100; int n,m,k, b[maxn][maxk], s[maxn][maxk], dfw[maxn][maxn], d[maxn][maxn], g[maxn][maxn], a[maxn][maxn]; void solve() { cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for(int j = 1; j <= k; j++) { cin >> b[i][j]; if(b[i][j] == -1) b[i][j] = inf; cin >> s[i][j]; if(s[i][j] == -1) s[i][j] = -inf; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dfw[i][j] = inf1; } } for(int i = 1; i <= m; i++) { int u,v,w; cin >> u >> v >> w; dfw[u][v] = min(dfw[u][v],w); } for(int v = 1; v <= n; v++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dfw[i][j] = min(dfw[i][j], dfw[i][v]+dfw[v][j]); } } } for(int u = 1; u <= n; u++) { for(int v = 1; v <= n; v++) { a[u][v] = 0; //compra em u e vende em v for(int i = 1; i <= k; i++) { a[u][v] = max(a[u][v],s[v][i]-b[u][i]); } // cout << u << " " << v << " " << dfw[u][v] << endl; } } int l = 1; int r = inf1; //valor maximo int ans = 0; while(l <= r) { int mid = (l+r)>>1; //cria as arestas for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = -inf1; } } for(int u = 1; u <= n; u++) { for(int v = 1; v <= n; v++) { g[u][v] = a[u][v]-dfw[u][v]*mid; d[u][v] = g[u][v]; // cout << u << " " << v << " " << d[u][v] << endl; } } bool ok = false; for(int v = 1; v <= n; v++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = max(d[i][j], d[i][v]+d[v][j]); } } } for(int i = 1; i <= n; i++) { // cout << d[i][i] << endl; if(d[i][i] >= 0) ok = true; } //encontrar se tem ciclo positivo em um grafo bellman // bool ok = false; // for(int beg = 1; beg <= n; beg++) { // for(int i = 1; i <= n; i++) { // d[i][0] = -inf; // } // d[beg][0] = 0; // for(int i = 1; i <= n+1; i++) { // for(int u = 1; u <= n; u++) d[u][i] = d[u][i-1]; // for(int u = 1; u <= n; u++) { // for(int v = 1; v <= n; v++) { // d[v][i] = max(d[v][i],d[u][i-1] + g[u][v]); // } // } // } // for(int u = 1; u <= n; u++) { // for(int v = 1; v <= n; v++) { // if(d[u][n] != -inf && d[v][n] < d[u][n]+g[u][v]) { // cout << beg << " " << u << " " << v << " " << d[u][n] << " " << d[v][n] << " " << g[u][v] << endl; // ok = true; // } // // d[v][i] = max(d[v][i],d[u][i-1] + g[u][v]); // } // } // } if(ok) { ans = mid; l = mid+1; } else { r = mid-1; } } cout << ans << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...