Структуры данных: определить все пары чисел (h, s), при которых компания h контролирует компанию s - C#

Узнай цену своей работы

Формулировка задачи:

Всем добрый вечер! Пытался решать через двумерный массив,вылетает постоянно за границу...Да и дальше как именно выбрать 50% и подвладельцев не знаю... Помогите пожалуйста написать это чудо Заранее спасибо за помощь! Условие Некоторые компании являются совладельцами других компании, так как приобрели часть их акций. Говорят, что компания А контролирует компанию В, если имеет место по меньшей мере одно из следующих условий: · А=В; · А владеет более, чем 50% акций В; · А контролирует k (k>0) компаний С1,…,Сk таких, что компания Сi владеет соответственно Xi% акций компании В (i=1,…,k) и Х1+Х2+ …+Хk>50%. Необходимо определить все пары чисел (h, s), при которых компания h контролирует компанию s. Входные данные: input.txt Во входном файле задается последовательность троек (i, j, p), которые означают, что компания i владеет p% акций компании j. Общее число компаний не превышает 100. Выходные данные: output.txt Выходные данные заносятся в файл, каждая строка которого соответствует найденной паре (h, s) (элементы в строке разделены пробелом). Пары упорядочены лексикографически. Пример input.txt 2 3 25 1 4 36 4 5 63 2 1 48 3 4 30 4 2 52 5 3 30 output.txt 4 2 4 3 4 5
Парни очень нужна помощь

Решение задачи: «Структуры данных: определить все пары чисел (h, s), при которых компания h контролирует компанию s»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.IO;
 
namespace CompanyProblem
{
    using Grapth = List<List<int>>;
    class Program
    {
        private readonly static Grapth _g = new Grapth();
        private static readonly int[,] _stock = new int[100,100];
        private static int _c;
        private static void BuildGraph(TextReader reader)
        {
            string line;
            var lines = new List<string>(100);
            while (!string.IsNullOrEmpty(line = reader.ReadLine()))
                lines.Add(line);
            for (int i = 0; i < 100; ++i)
                _g.Add(new List<int>());
            InitStock(lines.Count);
            foreach (var s in lines)
            {
                var ss = s.Split();
                int i = int.Parse(ss[0]) - 1;
                int j = int.Parse(ss[1]) - 1;
                int p = int.Parse(ss[2]);
                _g[i].Add(j);
                _stock[i, j] = p;
            }
        }
 
        private static void InitStock(int size)
        {
            //_stock = new int[size, size];
            for (int i = 0; i < _stock.GetLength(0); ++i)
                for (int j = 0; j < _stock.GetLength(1); ++j)
                    _stock[i, j] = 0;
        }
 
        private static void Resolve(TextReader reader, TextWriter writer)
        {
            BuildGraph(reader);
            for (_c = 0; _c < _g.Count; ++_c)
                for (int v = 0; v < _g.Count; ++v)
                    Dfs(v);
            var res = GetResult();
            Print(res, writer);
        }
 
        private static void Dfs(int v)
        {
            if (_stock[_c, v] <= 50 || _c == v)
                return;
            foreach (var t in _g[v])
            {
                _stock[_c, t] += _stock[v, t];
                Dfs(t);
            }
        }
 
        private static IEnumerable<string> GetResult()
        {
            var res = new List<string>();
            int size = _stock.GetLength(0);
            for (int i = 0; i < size; ++i)
                for (int j = 0; j < size; ++j)
                    if (_stock[i, j] > 50)
                        res.Add(string.Format("{0} {1}", i + 1, j + 1));
            res.Sort();
            return res;
        }
 
        private static void Print(IEnumerable<string> res, TextWriter writer)
        {
            foreach (var s in res)
                writer.WriteLine(s);
        }
 
        static void Main()
        {
            using (var reader =  new StreamReader("input.txt") /* Console.In*/)
            using (var writer = new StreamWriter("output.txt")/* Console.Out*/)
                Resolve(reader, writer);
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.4 из 5
Похожие ответы