Cykl o największej średniej wartości

Question

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.

Comments

Znalazłem taki artykuł. Jeśli nie chcesz zaglądać do artykułu to hint jest taki, żeby pozmieniać wagi krawędzi, aby były nieujemne, ale sumy na cyklach były zachowane. Wtedy łatwo znaleźć cykl o sumie 0.