Graph algorithm in C using Adjacency's list -- 2
Budget: $10 – $30 USD
wormholes
A given intergalactic empire needs to create a network between its planets using wormholes, which connect its planets.
To achieve this goal it is necessary to use purple matter to maintain a
network working inside the wormholes.
Since the empire wants to spend as little purple matter as possible,
they hire a bright computer arts student to solve
this problem efficiently.
The empire will cede the planets and the cost in purple matter of each connection of the
wormhole, and requires minimal cost to maintain the network between these
planets.
important criteria
Regardless of test results or non-compliance with the criteria below
will result in a zero score for this activity. Any questions please contact us.
You must solve this problem using graphs, and using the algorithm of
Kruskal (implementing the separate sets as a forest, using heuristic path compression and using union-by-rank).
Comments
You should include, at the beginning of your program, a brief header containing at
least your name and RA.
Properly indenting your code and including comments in your progress
program.
Accepted languages: C
Prohibited
The first line of the input consists of two integers n m, where
1 <= n <= 1000 and 0 <= m <= n(n - 1)/2, representing the number of planets
and the number of wormholes, respectively.
Each planet is represented by a numerical code between 0 and n - 1.
Each of the next m lines consists of a trio of integers u v w,
separated by space, where 0 <= u, v <= n - 1, which represents the existence
from a wormhole between planets coded u and v, and
-100 <= w <= 100, which represents the amount of purple matter needed
to make the network work inside the wormhole.
Exit
Your program's response must consist of a single integer z, representing
the minimum amount of purple matter needed to maintain the entire network
between the working planets.
examples
test 01
Prohibited:
3 3
0 1 -5
0 2 20
1 2 10
Exit:
5
Test 02
Prohibited:
6 7
0 1 -10
0 2 -20
1 3 -5
1 4 20
2 3 -1
3 5 15
4 5 10
Exit:
-11
Test 03
Prohibited:
5 10
0 1 25
0 2 10
0 3 4
0 4 65
1 2 15
1 3 54
1 4 87
2 3 65
2 4 99
3 4 70
Exit:
94
A given intergalactic empire needs to create a network between its planets using wormholes, which connect its planets.
To achieve this goal it is necessary to use purple matter to maintain a
network working inside the wormholes.
Since the empire wants to spend as little purple matter as possible,
they hire a bright computer arts student to solve
this problem efficiently.
The empire will cede the planets and the cost in purple matter of each connection of the
wormhole, and requires minimal cost to maintain the network between these
planets.
important criteria
Regardless of test results or non-compliance with the criteria below
will result in a zero score for this activity. Any questions please contact us.
You must solve this problem using graphs, and using the algorithm of
Kruskal (implementing the separate sets as a forest, using heuristic path compression and using union-by-rank).
Comments
You should include, at the beginning of your program, a brief header containing at
least your name and RA.
Properly indenting your code and including comments in your progress
program.
Accepted languages: C
Prohibited
The first line of the input consists of two integers n m, where
1 <= n <= 1000 and 0 <= m <= n(n - 1)/2, representing the number of planets
and the number of wormholes, respectively.
Each planet is represented by a numerical code between 0 and n - 1.
Each of the next m lines consists of a trio of integers u v w,
separated by space, where 0 <= u, v <= n - 1, which represents the existence
from a wormhole between planets coded u and v, and
-100 <= w <= 100, which represents the amount of purple matter needed
to make the network work inside the wormhole.
Exit
Your program's response must consist of a single integer z, representing
the minimum amount of purple matter needed to maintain the entire network
between the working planets.
examples
test 01
Prohibited:
3 3
0 1 -5
0 2 20
1 2 10
Exit:
5
Test 02
Prohibited:
6 7
0 1 -10
0 2 -20
1 3 -5
1 4 20
2 3 -1
3 5 15
4 5 10
Exit:
-11
Test 03
Prohibited:
5 10
0 1 25
0 2 10
0 3 4
0 4 65
1 2 15
1 3 54
1 4 87
2 3 65
2 4 99
3 4 70
Exit:
94