Cześć.
Próbuję rozwiązać takie zadanie: https://szkopul.edu.pl/problemset/problem/-xO_ABE0lLfiSnSd7Mvvrblx/site/?key=statement
Mam dany graf skierowany, ważony i chcę znaleźć cykl o największej średniej wartości wag na krawędziach. W książce pisze, żeby wynik wyszukać binarnie, jak sprawdzamy czy da się ułożyć wartość x, to odejmujemy od wagi na każdej krawędzi x i sprawdzamy za pomocą algorytmu Belmana Forda / Floyda Warshalla czy istnieje cykl o sumie >= 0. Wszystko jest jasne, ale mam pewien problem. Umiem za pomocą tych algorytmów sprawdzić czy istnieje cykl o sumie > 0, ale nie umiem sprawdzić, czy istnieje cykl o sumie = 0. Jak ktoś ma jakiś pomysł jak sprawdzić, czy istnieje w grafie cykl o sumie równej 0, to byłbym wdzięczny za podpowiedź.
Mam taki kod, dostaje 60pkt, właśnie przez to = 0:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()
struct Krawedz
{
int a,b,c;
};
const int MAXN = 105, INF = 1e9+50;
int n = 0, m = 0, a = 0, b = 0, c = 0;
ld poczatek = 0, koniec = 1e8+20, srodek = 0, eps = 0.0001;
vector<Krawedz> krawedzie;
ld dist[MAXN];
inline bool check_more_zero(ld x) // czy po odjeciu od kazdej krawedzi x, istnieje cykl o sumie > 0
{
for(int i = 1; i <= n; ++i) dist[i] = (ld)INF;
dist[1] = 0;
for(int step = 1; step <= n; ++step)
{
bool czy = false;
for(auto y : krawedzie)
{
ld odl = (ld)dist[y.a] + -((ld)y.c - x);
if(odl < dist[y.b])
{
dist[y.b] = odl, czy = true;
}
}
if(czy and step == n) return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
rep(i,m)
{
cin >> a >> b >> c;
krawedzie.pb({a,b,c});
}
while(koniec - poczatek > eps)
{
srodek = (poczatek + koniec) / (ld)2;
if(check_more_zero(srodek)) poczatek = srodek;
else koniec = srodek;
}
cout << fixed << setprecision(4) << poczatek << '\n';
return 0;
}
Z góry dziękuję za pomoc i poświęcony czas.
