ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1982. Electrification Plan

What is my code doing?
Posted by Nithin 16 May 2017 22:38
I have implemented a greedy algorithm to solve this problem and it got accepted and after reading the discussion I have noticed that many people used Prims algorithm to solve.
I have no idea of what Prims algorithm is. Could anyone please tell me what exactly is my code doing and how is it different from Prims algorithm?

#include <iostream>

const int MAXN = 101;
using namespace std;

int cost[MAXN][MAXN];
bool isPowerStation[MAXN];

int main()
{
    int n, k;
    scanf(" %d%d", &n, &k);

    for(int i = 0; i < k; i++)
    {
        int foo;
        scanf(" %d", &foo);
        isPowerStation[foo] = 1;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf(" %d", &cost[i][j]);

    int ans = 0;

    k = n -k;
    while(k--)
    {
        int index = -1, min_cost = 1 << 30;
        for(int i = 1; i <= n; i++)
        {
            if(isPowerStation[i])
            {
                for(int j = 1; j <= n; j++)
                {
                    if(!isPowerStation[j])
                    {
                        if(cost[i][j] < min_cost)
                        {
                            min_cost = cost[i][j];
                            index = j;
                        }
                    }
                }
            }
        }

        isPowerStation[index] = 1;
        ans += min_cost;
    }

    printf("%d\n", ans);
    return 0;
}
Re: What is my code doing?
Posted by Mahilewets 17 May 2017 20:12
There are only three algorithms for finding minimal spanning.  Their complexities are different,  but idea is the same.  So,  we can say that they all are actually the same algorithm.  Your code is most similar to Kruskal's algo.
You arr finding the smallest edge and adding it to MST.