Problem ze zrozumieniem zadania grafowego

Mam takie zadanie:

Bajtocja
Limit pamięci: 32 MB

Za górami, za lasami, za rzekami, za morzami leży kraj potężny i bogaty zwany Bajtocją. Panuje tam dobrotliwy król Bajtazar I Wielki, słynny ze swej troski o infrastrukturę kraju. W Bajtocji znajduje się miast. Władca rozkazał swym nadwornym architektom przygotować projekty nowych ponaddźwiękowych traktów konnych. Jako odpowiedź otrzymał propozycji, każda z nich składa się z trzech liczb p, k, w, gdzie p i k są miastami końcowymi traktu (trakt łączy te miasta bezpośrednio i nie przebiega przez inne miasta), a oznacza koszt zbudowania tego traktu. Każdym traktem można podróżować zarówno z miasta do , jak i w stronę przeciwną. Zamierzeniem króla jest budowa sieci traktów w taki sposób, aby można było nimi przejechać między każdymi dwoma miastami, być może odwiedzając po drodze inne miejscowości. Bajtazar jest bardzo oszczędnym królem, więc postanowił zgodzić się tylko na taką sieć, która będzie możliwie najtańsza.
Zadanie

Opracuj program, który:

wczyta ze standardowego liczbę miast, liczbę proponowanych traktów oraz opisy tych traktów,
dla każdego traktu określi, czy istnieje taka sieć połączeń między miastami, zgodna z królewskimi rozkazami i w której rozpatrywany trakt, wybudowany za wskazaną kwotę, jest wykorzystywany,
wypisze na standardowe wyjście zestawienie uzyskanych wyników.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite: liczbę miast n i liczbę proponowanych traktów m, rozdzielone pojedynczą spacją i spełniające warunki 2 <= n <= 7.000, 1<=m<=300.000 . Każdy z kolejnych wierszy zawiera po trzy liczby całkowite p, k, w rozdzielone pojedynczymi spacjami, opisujące proponowany trakt, przy czym p i k oznaczają miasta będące końcami traktu, zaś w jest ceną budowy tego traktu (1 <= p, k <= n, 1 <= w <= 100.000 ).

Wyjście
W każdym z kolejnych wierszy należy wypisać słowo "TAK" albo "NIE", w zależności od tego, czy można skonstruować plan budowy zgodny z życzeniem króla, dla którego trakt opisany w odpowiednim wierszu jest w nim zawarty. Możesz bezpiecznie założyć, że dla danych wejściowych zawsze istnieje plan budowy spełniający wymogi Bajtazara.
Przykład

Dla danych wejściowych:

6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3

poprawną odpowiedzią jest:

TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK

Narysowałem ten graf (różowe węzły to te trakty których król nie chce zbudować)

Skoro Król chce najtańszą sieć dróg to po co np. buduje tyle połączeń z pierwszym miastem ? Przecież wystarczyłoby jedno
LINK DO ZADANIA
TUTAJ TESTUJE

Skoro Król chce najtańszą sieć dróg to po co np. buduje tyle połączeń z pierwszym miastem ? Przecież wystarczyłoby jedno

Taką mu zaproponowali, a trzeba wybrać optymalne połączenie (odrzucić najdłuższe niepotrzebne). Czyli znaleźć minimum Spanning Tree:
https://en.wikipedia.org/wiki/Minimum_spanning_tree

To dlaczego nie wybrał takiej ścieżki ?

Wszystkie miasta są połączone najtaniej żółtymi traktami, po co królowi te zielone?

Źle zrozumiałeś treść zadania i wyjście programu.

Czy w tym zadaniu chodzi o circle property?

Najciezsza krawedz w cyklu nie nalezy do zadnego MST

Okej już chyba rozumiem, trzeba sprawdzić czy z danym traktem można stworzyć sieć dróg o minimalnej wartości, czy się mylę?

Jest jakiś algorytm z którym wymusiłbym szukanie MST wraz z podanym przeze mnie węzłem ?

stivens napisał(a):

Czy w tym zadaniu chodzi o circle property?

Najciezsza krawedz w cyklu nie nalezy do zadnego MST

Bierzesz wage krawedzi i jeden z koncow. DFSem lub BFSem przechodzisz (zaczynajac od wierzcholka z tej krawedzi) tylko te krawedzie ktore maja wage mniejsza "limitowi".

Jesli oba konce krawedzi zostana odwiedzone to krawedz lezy na cyklu i jest w nim "ostro" najciezsza

Ciekawostka, znalazłem algorytm na cs.stackexchange, zinterpretowałem, zaimplementowałem i czasy są boskie:

 	Test 	Wynik 	Czas 	Wynik
	1 	OK 	0.00s / 0.10s 	9 / 9
	2 	OK 	0.00s / 0.10s 	9 / 9
	3 	OK 	0.00s / 0.10s 	9 / 9
	4 	OK 	0.01s / 0.20s 	9 / 9
	5 	OK 	0.02s / 1.00s 	9 / 9
	6 	OK 	0.06s / 1.00s 	9 / 9
	7 	OK 	0.16s / 3.50s 	9 / 9
	8 	OK 	0.31s / 3.50s 	9 / 9
	9 	OK 	0.47s / 4.00s 	9 / 9
	10 	OK 	0.47s / 7.50s 	9 / 9
	11 	OK 	0.47s / 9.00s 	10 / 10

O(m log m + n)
Ale nie do końca jestem zadowolony, bo sam bym na taki algorytm nie wpadł ;/

@stivens nie rozumiem w czym pomoże mi to cycle properyty, weźmy przykład testowy, dla krawędzi o wadze 5 stworzy się koło ale dla krawędzi o wadze 4 też, dopiero w krawędzi o wadze 3 nie stworzy się koło, w czym mi to pomaga?

Suchy702 napisał(a):

@stivens nie rozumiem w czym pomoże mi to cycle properyty, weźmy przykład testowy, dla krawędzi o wadze 5 stworzy się koło ale dla krawędzi o wadze 4 też, dopiero w krawędzi o wadze 3 nie stworzy się koło, w czym mi to pomaga?

Pokaz ten cykl dla 4. Bo przy tej krawedzi BFSem mozesz chodzic tylko po takich co maja co najwyzej 3. Wiec gdzie sie cykl stworzy? :P

Chodzi o to ze jak masz krawedz to ona ma dwa konce. I sprawdzasz czy drugi koniec bedzie odwiedzony a nie czy cykl sie pojawia w ogolnosci

Napisałem to co mi radziłeś ale nie wiem w dwóch testach zła odpowiedź a w kilku przekroczono limit czasu

#include <bits/stdc++.h>

using namespace std;

struct trakt{
    int p;
    int k;
    int w;
};

bool bfs(vector<vector<pair<int, int>>> & graf, int limit, int p, int k){
    queue<int> kolejka;
    vector<bool> seen(graf.size());
    for (pair<int, int> next_node : graf[p]){
        if (next_node.first != k && next_node.second < limit){
            kolejka.push(next_node.first);
            seen[next_node.first] = true;
        }

    }
    int curr_node;
    while (kolejka.size() > 0){
        curr_node = kolejka.front();
        kolejka.pop();
        for (pair<int, int> next_node : graf[curr_node]){
            if (next_node.second < limit && seen[next_node.first] == false){
                if (next_node.first == k)
                    return false;
                kolejka.push(next_node.first);
                seen[next_node.first] = true;
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> graf(n+1);
    vector<trakt> trakty(m);
    for (int i = 0; i < m; i++){
        cin >> trakty[i].p >> trakty[i].k >> trakty[i].w;
        graf[trakty[i].p].push_back(make_pair(trakty[i].k, trakty[i].w));
        graf[trakty[i].k].push_back(make_pair(trakty[i].p, trakty[i].w));
    }

    for (trakt curr_trakt : trakty){
        if (bfs(graf, curr_trakt.w, curr_trakt.p, curr_trakt.k))
            cout << "TAK\n";
        else
            cout << "NIE\n";
    }
  return 0;
}

Chyba powinienem posortować wartości tych wag i to zrobić binaey searchem (wtedy znajde tą graniczą wartość w log m i bedę mógł odpowiadać na zapytania w czasie stałym )czy to nie ma sensu?

Macie jakiś pomysł na szybsze rozwiązanie tego zadania ? sprawdzanie dla każdej krawędzi czy tworzy cykl jest za wolne :(

Suchy702 napisał(a):

Macie jakiś pomysł na szybsze rozwiązanie tego zadania ? sprawdzanie dla każdej krawędzi czy tworzy cykl jest za wolne :(

Na poprzedniej stronie jest odnośnik do algorytmu w jednym z komentarzy.
W skrócie:

• Posortuje krawędzie po wagach.
• W kolejnych krokach tworzy się nowy graf, dodając krawędzie wg. rosnącej kolejności wag (wszystkie krawędzie o tej samej wadze przetwarza się razem):
• Sprawdź czy krawędzie o danej wadze tworzą cykl z krawędziami o mniejszych wagach. Można do tego wykorzystać Find-Union
• Dodaj wszystkie krawędzie o danej wadze do grafu (/ do zbioru rozłącznego.).
• Powtórz na następnych w kolejności krawędziach.

Tylko co to za limity, ze m^2 dostaje timeouta a mlogm robi to w 1/10 limitu czasu?

Kombinowałem z numpy, ale to jest taka kupa, że i tak się w limitach nie zmieściło:

#!/usr/bin/env python3
import numpy as np

n, m = map(int, input().split())

disjoint_set_parents = np.fromiter(range(n), dtype=np.int)
disjoint_set_ranks = np.zeros(n, dtype=np.int)


def disjoint_set_find_root(x):
    while x != disjoint_set_parents[x]:
        disjoint_set_parents[x] = disjoint_set_parents[disjoint_set_parents[x]]
        x = disjoint_set_parents[x]
    return x


def disjoint_set_merge(v1, v2):
    v1 = disjoint_set_find_root(v1)
    v2 = disjoint_set_find_root(v2)
    if v1 == v2:
        return
    if disjoint_set_ranks[v1] > disjoint_set_ranks[v2]:
        v1, v2 = v2, v1
    disjoint_set_parents[v2] = v1
    if disjoint_set_ranks[v1] == disjoint_set_ranks[v2]:
        disjoint_set_ranks[v1] += 1


edges_heaviness = np.full(m, False, dtype=np.bool)
edges = np.empty((m, 4), dtype=np.int)

for i in range(m):
    p, k, w = map(int, input().split())
    edges[i] = [i, p - 1, k - 1, w]

edges.view('int,int,int,int').sort(order=['f3'], axis=0)

start = 0
while start < m:
    stop = start + 1
    while stop < m and edges[start, 3] == edges[stop, 3]:
        stop += 1
    for index in range(start, stop):
        edges_heaviness[edges[index, 0]] = \
            disjoint_set_find_root(edges[index, 1]) == \
            disjoint_set_find_root(edges[index, 2])
    for index in range(start, stop):
        disjoint_set_merge(edges[index, 1], edges[index, 2])
    start = stop

for super_heavy in edges_heaviness:
    print("NIE" if super_heavy else "TAK")