Ĺadny brzuch
Tresc zadania:
"Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek występuje dokładnie raz.
B - Bez bajki dla dorosłych. (IV WMIF, contest lokalny)
Dla zadanego grafu nieskierowanego o v wierzchołkach i e krawędziach rozstrzygnąć, czy istnieje w nim cykl Hamiltona.
Wejście
W pierwszej linii wejścia znajduje się mała liczba naturalna D, oznaczająca liczbę przypadków testowych. W pierwszej linii każdego przypadku podane są dwie liczby całkowite 0<v<17, 0<e<106, oznaczające odpowiednio ilość wierzchołków i krawędzi w danym grafie. W kolejnych e liniach znajdują się pary liczb 1<=a,b<=v – opisy kolejnych krawędzi grafu.
Wyjście
Wyjście powinno zawierać dokładnie D linii, po jednej dla każdego przypadku testowego. W i-tej linii należy wypisać 0, jeśli w i-tym grafie istnieje cykl Hamiltona, 1 w przeciwnym wypadku.
Przykład
IN:
1
3 4
1 2
1 3
2 3
2 1
OUT:
0
Mój kod na to jest taki:
#include<cmath> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> G[18]; int V, E; queue<int> q; bool visited[18], OK=false; bool istnieje[18][18]; void DFSHamilton(int v) { q.push(v); if(q.size() == V) { bool test = false; for(vector<int>::iterator i = G[v].begin(); i != G[v].end(); i++) if((*i) == 1) { OK=true; break; } } else { visited[v] = true; for(vector<int>::iterator x = G[v].begin(); x != G[v].end(); x++) if(!visited[* x]) DFSHamilton(* x); visited[v] = false; } q.pop(); } main() { int n; scanf("%d", &n); while(n--) { int a, b; bool mozna=true, wszystkie=true; for(int i=0; i<=18; i++) visited[i]=false; for(int i=0; i<=18; i++) for(int j=0; j<=18; j++) istnieje[i][j]=false; for(int i=0; i<=V; i++) G[i].clear(); OK=false; scanf("%d %d", &V, &E); for(int i=0; i<E; i++) { scanf("%d %d", &a, &B); if(a!=b && !istnieje[a][b] && !istnieje[b][a]) { G[a].push_back(B); G[b].push_back(a); istnieje[a][b]=true; istnieje[b][a]=true; } else { i--; E--; } } if(V>=3) { for(int i=1; i<=V; i++) { if(G[i].size() < ceil(float(V)/2)) wszystkie=false; } if(wszystkie) { printf("%d\n", 0); mozna=false; } } if(mozna) { if((E>=(((V-1)*(V-2))/2+2) || E==(n*(n-1))/2)) printf("%d\n", 0); else { DFSHamilton(1); printf("%d\n", !OK); } } } system("pause"); }
W naszej szkolnej testerce przekracza on limit czasu (dostaję 66/100 pkt). Ale jest to problem NP-trudny, wiec algorytmicznie nic (prawda?) nie wyciagne. Wiec pozostaje mi jedynie korzystanie z twierdzen... W komentarzu znajduje sie proba uzycia jednego z nich (tego). A jest ono w komentarzu, gdyz jak je dam w normalnym kodzie, to dostaje 0 pkt (czyli mam bledna odpowiedz juz na wstepie). Moje pytanie brzmi: jak przyspieszyc ten program i czemu po zastosowaniu tego twierdzenia progs sie psuje (no chyba ze ja to twierdzenie zle rozumiem... a rozumiem je tak: |V(G)| - ilosc wierzcholkow, deg(v) - ilosc wychodzacych krawedzi z kazdego wierzcholka, n - takze ilosc wierzcholkow)?
//Edit: Heh, slepota nie boli xD Znalazlem blad, teraz jest ok, ale wciaz nie mam 100... mam 83... gdzie jeszcze moge przyspieszyc to?
Użytkownik _Herkules_ edytował ten post 22 luty 2008, 23:04
Powód edycji: codebox
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
"Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek występuje dokładnie raz.
B - Bez bajki dla dorosłych. (IV WMIF, contest lokalny)
Dla zadanego grafu nieskierowanego o v wierzchołkach i e krawędziach rozstrzygnąć, czy istnieje w nim cykl Hamiltona.
Wejście
W pierwszej linii wejścia znajduje się mała liczba naturalna D, oznaczająca liczbę przypadków testowych. W pierwszej linii każdego przypadku podane są dwie liczby całkowite 0<v<17, 0<e<106, oznaczające odpowiednio ilość wierzchołków i krawędzi w danym grafie. W kolejnych e liniach znajdują się pary liczb 1<=a,b<=v – opisy kolejnych krawędzi grafu.
Wyjście
Wyjście powinno zawierać dokładnie D linii, po jednej dla każdego przypadku testowego. W i-tej linii należy wypisać 0, jeśli w i-tym grafie istnieje cykl Hamiltona, 1 w przeciwnym wypadku.
Przykład
IN:
1
3 4
1 2
1 3
2 3
2 1
OUT:
0
Mój kod na to jest taki:
#include<cmath> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> G[18]; int V, E; queue<int> q; bool visited[18], OK=false; bool istnieje[18][18]; void DFSHamilton(int v) { q.push(v); if(q.size() == V) { bool test = false; for(vector<int>::iterator i = G[v].begin(); i != G[v].end(); i++) if((*i) == 1) { OK=true; break; } } else { visited[v] = true; for(vector<int>::iterator x = G[v].begin(); x != G[v].end(); x++) if(!visited[* x]) DFSHamilton(* x); visited[v] = false; } q.pop(); } main() { int n; scanf("%d", &n); while(n--) { int a, b; bool mozna=true, wszystkie=true; for(int i=0; i<=18; i++) visited[i]=false; for(int i=0; i<=18; i++) for(int j=0; j<=18; j++) istnieje[i][j]=false; for(int i=0; i<=V; i++) G[i].clear(); OK=false; scanf("%d %d", &V, &E); for(int i=0; i<E; i++) { scanf("%d %d", &a, &B); if(a!=b && !istnieje[a][b] && !istnieje[b][a]) { G[a].push_back(B); G[b].push_back(a); istnieje[a][b]=true; istnieje[b][a]=true; } else { i--; E--; } } if(V>=3) { for(int i=1; i<=V; i++) { if(G[i].size() < ceil(float(V)/2)) wszystkie=false; } if(wszystkie) { printf("%d\n", 0); mozna=false; } } if(mozna) { if((E>=(((V-1)*(V-2))/2+2) || E==(n*(n-1))/2)) printf("%d\n", 0); else { DFSHamilton(1); printf("%d\n", !OK); } } } system("pause"); }
W naszej szkolnej testerce przekracza on limit czasu (dostaję 66/100 pkt). Ale jest to problem NP-trudny, wiec algorytmicznie nic (prawda?) nie wyciagne. Wiec pozostaje mi jedynie korzystanie z twierdzen... W komentarzu znajduje sie proba uzycia jednego z nich (tego). A jest ono w komentarzu, gdyz jak je dam w normalnym kodzie, to dostaje 0 pkt (czyli mam bledna odpowiedz juz na wstepie). Moje pytanie brzmi: jak przyspieszyc ten program i czemu po zastosowaniu tego twierdzenia progs sie psuje (no chyba ze ja to twierdzenie zle rozumiem... a rozumiem je tak: |V(G)| - ilosc wierzcholkow, deg(v) - ilosc wychodzacych krawedzi z kazdego wierzcholka, n - takze ilosc wierzcholkow)?
//Edit: Heh, slepota nie boli xD Znalazlem blad, teraz jest ok, ale wciaz nie mam 100... mam 83... gdzie jeszcze moge przyspieszyc to?
Użytkownik _Herkules_ edytował ten post 22 luty 2008, 23:04
Powód edycji: codebox