Структуры данных: определить все пары чисел (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);
}
}
}