Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
casa verde 2024

Intrerupator cu N - doza doar cu ...

Incalzire casa fara gaz/lemne

Incalzire in pardoseala etapizata
 Suprataxa card energie?!

Cum era nivelul de trai cam din a...

probleme cu ochelarii

Impozite pe proprietati de anul v...
 teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...

Rezultat RMN
 Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD.
 

[TEMA] Arbore partial de cost minim (Kruskal) - depasire timp

- - - - -
  • Please log in to reply
15 replies to this topic

#1
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014
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 B)
{
	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
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
Titlul, mai pe romaneste? Vreo cerinta concreta?

Edited by dani.user, 23 April 2017 - 15:43.


#3
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014
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.


#4
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014
Deci totul e bine ?:))))

#5
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014
Deci chiar nu stie nimeni?Singura data cand nu primesc niciun raspuns

#6
lightpoint

lightpoint

    Member

  • Grup: Members
  • Posts: 785
  • Înscris: 16.02.2017

View Postjdavyd, on 01 mai 2017 - 07:42, said:

Deci chiar nu stie nimeni?Singura data cand nu primesc niciun raspuns
Si ce raspuns ai dori ?

Edited by lightpoint, 01 May 2017 - 08:52.


#7
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005

View Postjdavyd, on 01 mai 2017 - 07:42, said:

Deci chiar nu stie nimeni?Singura data cand nu primesc niciun raspuns
Iar noi nu stim cine iti da tie TLE si nici care este acea limita.
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.
despre heap si Prim ai citit ?

Edited by MarianG, 01 May 2017 - 09:19.


#8
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014

View PostMarianG, on 01 mai 2017 - 09:06, said:

Iar noi nu stim cine iti da tie TLE si nici care este acea limita.
Fa si tu niste masuratori si vezi un ai bottleneck.

p.s.

despre heap si Prim ai citit ?
Da stiu, dar aici nu aplic algoritmul lui Prim.

#9
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
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
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014

View PostMarianG, 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
Acolo este precizat algoritmului lui Kruskal si toate sursele pe care le-am vazut acolo, au folosit Kruskal.
La problema asta http://www.infoarena...problema/retea2 am sa incerc sa fac Prim (pt ca Kruskal nu e optim).

#11
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
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
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014

View Postdani.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.
Prim e mai optim cu putin decat Kruskal, dar aici se cere Kruskal
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
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
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.

Attached File  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
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014
Deci codul meu are un bug?

Edited by dani.user, 03 May 2017 - 16:55.
quote inutil


#15
jdavyd

jdavyd

    Member

  • Grup: Members
  • Posts: 323
  • Înscris: 24.07.2014

View Postjdavyd, on 03 mai 2017 - 09:37, said:

Deci codul meu are un bug?
O fi inutil dar nu inteleg, ce ai vrut sa zici...

#16
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
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

Chirurgia spinală minim invazivă 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

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate