Different solutions

[Snaksa]

Hello! I have been looking at the tasks that appear at school level competitions these days and found an interesting one. Here is the task:

In the country Waterland there are n lakes (numbered from 1 to n) and m channels between them. The width (in meters) of each channel is known. Navigate the channels can be performed in both directions. It is known that a boat with width of one meter can reach any lake, starting from lake number 1.
Write a program channels, which calculates the minimum number of channels that should be widened, so that a boat in width k meters can make a trip between every two lakes (the boat can move from one lake to another if its width is less than or equal to the width of the channel, connecting the lakes).

Input
On the first line of the standard input are given integers n and m (1 < n ≤ 1000, 1 < m ≤ 100000).
On each of the next m lines are given three integers i, j and w, showing that there is a channel of weight w (1 ≤ w ≤ 200) between lakes i and j (1 ≤ i, j ≤ n).
On the last line is given the integer k (1 ≤ k ≤ 200).

Output
On a line of the standard output the program must write one integer – the minimum number of channels that should be widened.

Example
Input
6 9
1 6 1
1 2 2
1 4 3
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
4
Output
2

The first thing that came to my mind was to build a graph and traverse through it. So I did it. Here is the code that I wrote. It checks every possible way and outputs the smallest value of channels that should be widened.

#include<iostream>
#include<list>
using namespace std;

//We create the structure
struct Point
	{
		int to;
		int width;
		Point(int t = 0, int w = 0)
			{
				to = t;
				width = w;
			}
	};

list<Point> Points[1000]; //Points of the graph
bool used[1000];//Store the used points
int min_to_be_changed = 201;
int count = 0;

void DFS(int start, int level, int n, int k) //Depth-First-Search
	{
		if(level == n-1)//Check if we have visited all the points of the graph
			{
				if(count < min_to_be_changed) min_to_be_changed = count;
				return;
			}
		list<Point>::iterator Iter = Points[start].begin();
		for(Iter; Iter != Points[start].end(); Iter++)//Check every path
			{
				if(!used[Iter->to])//If we haven't visited the point - go through it
					{
						used[Iter->to] = true;//make it visited
						if(Iter->width < k) count++;//if it is not wide enough add 1 to count

						DFS(Iter->to, level+1, n, k); // start DFS()

						used[Iter->to] = false;//Make it unvisited again
						if(Iter->width < k) count--;//if it was not wide enough substract 1 from count
					}
			}
	}

int main()
	{
		int n, m, k;
		cin >> n >> m;
		for(int i = 0; i < m; i++)
			{
				int from, to, width;
				cin >> from >> to >> width;
				Point New;
				New.to = to;
				New.width = width;
				Points[from].push_back(New);
				New.to = from;
				Points[to].push_back(New);
			}
		cin >> k;

		used[1] = true;
		DFS(1, 0, n, k);
		cout << endl;
		cout << min_to_be_changed << endl;

		system("pause");
		return 0;
	}

Everything is working well. Then I saw the solution that was given by the creator of the task. This is it:

#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <time.h>
#include <limits.h>
using namespace std;

const int MaxVertex=1001;
int E[MaxVertex][MaxVertex], D[MaxVertex], Pi[MaxVertex];
bool Marked[MaxVertex];
int N,M,K;


void input()
{
  int u,v,w;
  scanf("%d %d", &N, &M);
  for(int i=1; i<=N; i++)
   for (int j=1; j<=N; j++)
    E[i][j]=0;
  for(int i=1; i<=M; i++)
  {
   scanf("%d %d %d", &u, &v, &w);
   E[u][v]=w;
   E[v][u]=w;
  }
  scanf("%d", &K);
}

void CreateMST(int s)
{
  int u,v,w,cnt;
  for(int i=1; i<=N; i++)
   { D[i]=0; Pi[i]=-1; Marked[i]=false; }
  D[s]=INT_MAX;
  cnt=1;
  while (cnt<=N) {
   w=0; u=0;
   for(int i=1; i<=N; i++)
     if ((D[i]>w) && (!Marked[i]))
       {w=D[i]; u=i;}
   Marked[u]=true;
   for(int v=1; v<=N; v++)
     if ((D[v]<E[u][v]) && (!Marked[v]))
       {D[v]=E[u][v]; Pi[v]=u;}
   cnt++;
  }
}

void SolveP2()
{
  int l;
  l=0;
  for (int v=1; v<=N; v++)
   if ((Pi[v]>0) && (D[v]<K))
    l++;
  printf("%d\n",l);
}

main()
{
  input();
  CreateMST(1);
  SolveP2();
}

It is also working well but don't you think it's very complicated to use arrays?
I noticed that in many tasks like this, the creator's code is made with arrays, although it is very hard to read. Is there any reason to use more often arrays than to do the thing that I have done in my code. Everything can be simpler with a structure.
What do you think?

[Cubbi]

I noticed that in many tasks like this, the creator's code is made with arrays, although it is very hard to read.

It's just someone's old C solution, copied over and over.

Everything can be simpler with a structure. What do you think?

Certainly, and in C++, that structure is boost::adjacency_list

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

int main()
{
    using namespace boost;
    typedef adjacency_list<vecS, vecS, undirectedS, no_property,
                           property<edge_weight_t, int> > graph_t;

    int n, m;
    std::cin >> n >> m;

    graph_t g(m);

    // load the data into the graph
    property_map<graph_t, edge_weight_t>::type wmap = get(edge_weight, g);
    while(m-->0) {
        int i, j, w;
        std::cin >> i >> j >> w;
        // add the edge to the graph, use the channel width as edge weight
        wmap[add_edge(i, j, g).first] = w;
    }
    int k;
    std::cin >> k;

    // reset edge weights: 0 if already wide enough, 1 if needs widening
    graph_traits<graph_t>::edge_iterator ei, end;
    for(boost::tie(ei, end) = edges(g); ei != end; ++ei)
        wmap[*ei] = wmap[*ei] < k;

    // find MST
    typedef graph_traits<graph_t>::edge_descriptor edge_t;
    std::vector<edge_t> mst;
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst));

    // print the number of channels that need widening
    std::cout << count_if(mst.begin(), mst.end(), [&](edge_t e){
        return wmap[e] == 1;
    });
}

online demo http://coliru.stacked-crooked.com/a/5ce7995934a0761d

[Snaksa]

Thanks for the reply. Maybe you can tell me from whre I can learn more about this <boost> library? :)

[tipaye]

try

http://www.boost.org/

[Snaksa]

Thanks :)