Chirurgia spinală minim invazivă
Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical. Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale. www.neurohope.ro |
[TEMA] Arbore partial de cost minim (Kruskal) - depasire timp
Last Updated: May 04 2017 21:06, Started by
jdavyd
, Apr 23 2017 15:30
·
0
#1
Posted 23 April 2017 - 15:30
iau tle la aceasta problema. Ma poate ajuta cineva?
#include <iostream> #include <fstream> #include <algorithm> #include <vector> #define MAX 400100 using namespace std; ifstream fin("apm.in"); ofstream fout("apm.out"); struct edge { int x,y,cost; }; int parent[MAX]; int height[MAX]; vector <edge> graph; vector <edge> apcm; int cmp(edge a,edge { return a.cost<b.cost; } void read_graph(int &no_nodes,int &no_edges) { int i; fin>>no_nodes>>no_edges; edge e; for(i=1; i<=no_edges; i++) { fin>>e.x>>e.y>>e.cost; graph.push_back(e); } } int find_parent(int i) { if(parent[i]==i) return i; return find_parent(parent[i]); } void union_trees(int root1,int root2) { if(height[root1]>height[root2]) parent[root2]=root1; else if(height[root1]==height[root2]) { parent[root2]=root1; height[root1]++; } else { parent[root1]=root2; } } void kruskal(int no_nodes,int no_edges) { int i; int min_cost=0,nr_edges=0; int node1,node2,root1,root2; sort(graph.begin(),graph.end(),cmp); for(i=1; i<=no_nodes; i++) parent[i]=i; i=0; while(nr_edges<no_nodes-1) { node1=graph[i].x; node2=graph[i].y; root1=find_parent(node1); root2=find_parent(node2); if(root1!=root2) { nr_edges++; min_cost+=graph[i].cost; union_trees(root1,root2); apcm.push_back(graph[i]); } i++; } fout<<min_cost<<endl<<nr_edges<<endl; for(i=0; i<nr_edges; i++) fout<<apcm[i].x<<" "<<apcm[i].y<<endl; } int main() { int no_nodes,no_edges; read_graph(no_nodes,no_edges); kruskal(no_nodes,no_edges); return 0; } |
#2
Posted 23 April 2017 - 15:43
Titlul, mai pe romaneste? Vreo cerinta concreta?
Edited by dani.user, 23 April 2017 - 15:43. |
#3
Posted 23 April 2017 - 15:48
Algoritmul lui kruskal pt determinarea arborelui partial de cost minim
http://www.infoarena.ro/problema/apm iau TLE la ultimele 3 teste Edited by jdavyd, 23 April 2017 - 16:07. |
#5
Posted 01 May 2017 - 07:42
Deci chiar nu stie nimeni?Singura data cand nu primesc niciun raspuns
|
#6
Posted 01 May 2017 - 08:50
#7
Posted 01 May 2017 - 09:06
jdavyd, on 01 mai 2017 - 07:42, said:
Deci chiar nu stie nimeni?Singura data cand nu primesc niciun raspuns Fa si tu niste masuratori si vezi un ai bottleneck. p.s. Quote Pentru a se optimiza mai departe algoritmul pentru extragerea minimului se foloseste un heap, iar de fiecare data cand se introduce un nod in subarbore sunt parcurse muchiile incidente cu el si se actualizeaza nodurile vecine. Astfel complexitatea devine O(M*log2N). Algoritmul este cunoscut in literatura de specialitate ca Algoritmul lui Prim. O sursa pe acesta idee se poate vedea aici. Edited by MarianG, 01 May 2017 - 09:19. |
#8
Posted 01 May 2017 - 09:42
#9
Posted 01 May 2017 - 09:45
Si nu ai vrea sa incerci?
p.s. vezi ca pentru problema asta atat punctajul cat si sursa sunt vizibile Quote
6 Depăşit 2552kb Time limit exceeded. 0 7 Depăşit 4564kb Time limit exceeded. 0 8 212ms 1252kb Corect 10 9 92ms 1248kb Corect 10 10 Depăşit 3704kb Time limit exceeded. 0 Quote iau TLE la ultimele 3 teste Edited by MarianG, 01 May 2017 - 09:45. |
#10
Posted 01 May 2017 - 09:48
MarianG, on 01 mai 2017 - 09:45, said:
Si nu ai vrea sa incerci? p.s. vezi ca pentru problema asta atat punctajul cat si sursa sunt vizibile La problema asta http://www.infoarena...problema/retea2 am sa incerc sa fac Prim (pt ca Kruskal nu e optim). |
|
#11
Posted 01 May 2017 - 10:19
In programare lucram cu informatii cat mai concrete, nu "nu merge". Poate se trezesc intr-o zi si cei cu diverse siteuri de evaluare si ofera informatii complete.
Altfel, alt raspuns n-am decat: rasfoieste Cormen si cauta un algoritm mai optim... Nici sa testez codul tau n-am cum fiindca nu-mi spui cum arata intrarile necesare. Edited by dani.user, 01 May 2017 - 10:22. |
#12
Posted 01 May 2017 - 10:28
dani.user, on 01 mai 2017 - 10:19, said:
In programare lucram cu informatii cat mai concrete, nu "nu merge". Poate se trezesc intr-o zi si cei cu diverse siteuri de evaluare si ofera informatii complete. Altfel, alt raspuns n-am decat: rasfoieste Cormen si cauta un algoritm mai optim... Nici sa testez codul tau n-am cum fiindca nu-mi spui cum arata intrarile necesare. Restrictiile 1 ≤ N ≤ 200 000 1 ≤ M ≤ 400 000 -1 000 ≤ C ≤ 1 00 Pentru 20% din teste N, M ≤ 20 Pentru inca 20% din teste N ≤ 800 si M ≤ 1 500 |
#13
Posted 02 May 2017 - 21:40
Pasul 1
Rulez codul tau pe inputul mic de test. Pare ok Pasul 2 Generez un fisier de test cu N = 800 si M = 1 500. Rulez codul tau pe noul fisier generat => vector subscript out of range. i a ajuns deja la 1500 pe cand nr_edges e doar la 684. inputs.zip 699.28K 1 downloads node1 = graph[i].x; Pasul 3 Am scris o solutie conform descrierii algoritmului de pe Wikipedia (https://en.wikipedia...kal's_algorithm). Pentru a retine daca un nod apartine unui set, tin un vector de pointeri la seturi (shared_ptr poti sa-l vezi ca un pointer ce stie sa-si dea singur delete cand nu mai e nevoie de el). Comparatia intre cele doua seturi e triviala, o simpla comparatie de pointer. Unirea seturilor o fac pe principiul cel mare il inghite pe cel mic. #include <fstream> #include <cstdint> #include <map> #include <memory> #include <vector> #include <set> struct Input { uint32_t nrOfNodes; uint32_t nrOfEdges; std::multimap<int16_t, std::pair<int32_t, int32_t>> edgedSortedByCost; }; struct Output { int32_t totalCost; std::vector<std::pair<int32_t, int32_t>> minimumSpanningTreeEdges; }; Input readInput(std::ifstream& in) { Input result; in >> result.nrOfNodes; in >> result.nrOfEdges; int32_t x, y; int16_t cost; char buffer[16384]; in.rdbuf()->pubsetbuf(buffer, 16384); for (uint32_t i = 0; i < result.nrOfEdges; ++i) { in >> x >> y >> cost; result.edgedSortedByCost.insert(std::make_pair(cost, std::make_pair(x, y))); } return result; } auto createSetVector(uint32_t nrOfNodes) { std::vector<std::shared_ptr<std::set<int32_t>>> result(nrOfNodes + 1); for (uint32_t i = 0; i <= nrOfNodes; ++i) { result[i] = std::make_shared<std::set<int32_t>>(); result[i]->insert(i); } return result; } Output solveWithKruskal(Input& input) { auto sets = createSetVector(input.nrOfNodes); auto nrOfOutputEdgesNeeded = input.nrOfNodes - 1; Output output; output.totalCost = 0; for (auto& costEdgesPair : input.edgedSortedByCost) { auto& cost = costEdgesPair.first; auto& edges = costEdgesPair.second; auto& firstSet = sets[edges.first]; auto& secondSet = sets[edges.second]; if (firstSet != secondSet) { output.totalCost += cost; output.minimumSpanningTreeEdges.push_back(edges); std::shared_ptr<std::set<int32_t>> smallerSet, biggerSet; if (firstSet->size() < secondSet->size()) { smallerSet = firstSet; biggerSet = secondSet; } else { smallerSet = secondSet; biggerSet = firstSet; } for (auto& node : *smallerSet) { biggerSet->insert(node); sets[node] = biggerSet; } } if (output.minimumSpanningTreeEdges.size() >= nrOfOutputEdgesNeeded) { break; } } return output; } int main() { std::ifstream in("apm.in"); auto input = readInput(in); auto output = solveWithKruskal(input); std::ofstream out("apm.out"); out << output.totalCost << '\n'; out << output.minimumSpanningTreeEdges.size() << '\n'; for (auto& pair : output.minimumSpanningTreeEdges) { out << pair.first << ' ' << pair.second << '\n'; } } Edited by dani.user, 02 May 2017 - 21:41. |
#14
Posted 03 May 2017 - 09:37
Deci codul meu are un bug?
Edited by dani.user, 03 May 2017 - 16:55.
|
#15
Posted 04 May 2017 - 20:39
|
#16
Posted 04 May 2017 - 21:06
Descarca inputul ce l-am atasat si probeaza-l pe codul tau. Sper sa le fi generat corect.
Edited by dani.user, 04 May 2017 - 21:12. |
Anunturi
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users