Problem B. Full Binary Tree

#include <algorithm>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <string>
#include <vector>using std::cin;
using std::cout;
using std::endl;
using std::fstream;
using std::map;
using std::stringstream;
using std::string;
using std::vector;int
get_result(const vector<vector<int> > &_matrix);int
get_max(const vector<vector<int> > &_matrix, const int _child_row, const int _parent);int children_nodes[][];int main(int argc, char *argv[])
{
int case_amount = ;
cin >> case_amount; for (int i = ; i < case_amount; ++i)
{
memset(children_nodes, , sizeof(children_nodes)); int N = ;
cin >> N; // Step1: Init
vector<vector<int> > matrix(N + , vector<int>()); for (int j = ; j < N - ; ++j)
{
int row = , column = ;
cin >> row >> column; matrix[row].push_back(column);
matrix[column].push_back(row);
} const int result = get_result(matrix);
cout << "Case #" << + i << ": " << result << endl;
} return ;
}int
get_result(const vector<vector<int> > &_matrix)
{
int max = ;
for (int i = ; i < _matrix.size(); ++i)
{
const int result = get_max(_matrix, i, ); if (max < result)
max = result;
} return _matrix.size() - max - ;
}int
get_max(const vector<vector<int> > &_matrix, const int _child_row, const int _parent)
{
if ( == children_nodes[_child_row][_parent])
{
vector<int> children; for (int i = ; i < _matrix[_child_row].size(); ++i)
{
if (_parent != _matrix[_child_row][i])
children.push_back(get_max(_matrix, _matrix[_child_row][i], _child_row));
} std::sort(children.begin(), children.end(), std::greater<int>()); if (children.size() < )
children_nodes[_child_row][_parent] = ;
else
children_nodes[_child_row][_parent] = + children[] + children[];
} return children_nodes[_child_row][_parent];
}

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <string>
#include <vector>using std::cout;
using std::endl;
using std::fstream;
using std::map;
using std::stringstream;
using std::string;
using std::vector;fstream fs("input.txt", fstream::in);
fstream fout("output.txt", fstream::out);int
get_int_from_next_line();string
get_string_from_next_line();int
get_result(const vector<vector<int> > &_matrix);int
get_max(const vector<vector<int> > &_matrix, const int _child_row, const int _parent);int main(int argc, char *argv[])
{
if (fs.good())
{
const int case_amount = get_int_from_next_line(); for (int i = ; i < case_amount; ++i)
{
const int N = get_int_from_next_line(); // Step1: Init
vector<vector<int> > matrix(N, vector<int>()); for (int j = ; j < N - ; ++j)
{
const string line = get_string_from_next_line();
int row = , column = ;
stringstream temp_stream(line);
temp_stream >> row >> column; matrix[row-].push_back(column-);
matrix[column-].push_back(row-);
} const int result = get_result(matrix);
fout << "Case #" << + i << ": " << result << endl;
}
} fs.close();
fout.close();
return ;
}int
get_int_from_next_line()
{
string line = "";
getline(fs, line);
stringstream stream(line);
int temp = ;
stream >> temp;
return temp;
}string
get_string_from_next_line()
{
string line = "";
getline(fs, line);
return line;
}int
get_result(const vector<vector<int> > &_matrix)
{
int max = ;
for (int i = ; i < _matrix.size(); ++i)
{
int result = get_max(_matrix, i, -); if (max < result)
max = result;
} return _matrix.size() - max;
}int
get_max(const vector<vector<int> > &_matrix, const int _child_row, const int _parent)
{
vector<int> children; for (int i = ; i < _matrix[_child_row].size(); ++i)
{
if (_parent != _matrix[_child_row][i])
children.push_back(get_max(_matrix, _matrix[_child_row][i], _child_row));
} std::sort(children.begin(), children.end(), std::greater<int>()); if (children.size() < )
return ;
else
return + children[] + children[];
}

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <string>
#include <vector>using std::cout;
using std::endl;
using std::fstream;
using std::map;
using std::stringstream;
using std::string;
using std::vector;fstream fs("input.txt", fstream::in);
fstream fout("output.txt", fstream::out);int
get_int_from_next_line();string
get_string_from_next_line();int
get_result(vector<vector<int> > _matrix);int
get_max_children(const vector<vector<int> > &_matrix, const int _row, const int _column);int main(int argc, char *argv[])
{
if (fs.good())
{
const int case_amount = get_int_from_next_line(); for (int i = ; i < case_amount; ++i)
{
const int N = get_int_from_next_line(); // Step1: Init
vector<vector<int> > matrix(N, vector<int>(N, -)); for (int j = ; j < N - ; ++j)
{
const string line = get_string_from_next_line();
int row = , column = ;
stringstream temp_stream(line);
temp_stream >> row >> column; matrix[row-][column-] = -;
matrix[column-][row-] = -;
} const int result = get_result(matrix);
fout << "Case #" << + i << ": " << result << endl;
}
} fs.close();
fout.close(); return ;
}int
get_int_from_next_line()
{
string line = "";
getline(fs, line);
stringstream stream(line);
int temp = ;
stream >> temp;
return temp;
}string
get_string_from_next_line()
{
string line = "";
getline(fs, line);
return line;
}int
get_result(vector<vector<int> > _matrix)
{
if ( == _matrix.size())
{
return ;
}
else if ( == _matrix.size())
{
return ;
} // Step2: Preprocess
for (int row = ; row < _matrix.size(); ++row)
{
const int count_not_n2 = _matrix.size() - std::count(_matrix[row].begin(), _matrix[row].end(), -);
if ( == count_not_n2)
{
const vector<int>::const_iterator it = std::find(_matrix[row].begin(), _matrix[row].end(), -);
const int column = it - _matrix[row].begin();
_matrix[row][column] = ;
_matrix[column][row] = ;
}
} // Step3: loop
while (true)
{
bool isHasNegtiveOne = false;
for (int row = ; row < _matrix.size(); ++row)
{
const int count_1 = std::count(_matrix[row].begin(), _matrix[row].end(), -);
if ( < count_1)
isHasNegtiveOne = true; if ( == count_1)
{
const vector<int>::const_iterator r_it = std::find(_matrix[row].begin(), _matrix[row].end(), -);
const int column = r_it - _matrix[row].begin(); // Step: 3.1
{
vector<int> column_vec = _matrix[column];
column_vec.erase(row + column_vec.begin());
const vector<int>::const_iterator c_it = std::find(column_vec.begin(), column_vec.end(), -);
if (c_it == column_vec.end())
{
// Step: 3.2
const int column_max_children = get_max_children(_matrix, column, row);
_matrix[row][column] = + column_max_children;
}
} // Step: 3.3
// column as the parent, row as the child
// calculate how many nodes can row have
const int row_max_children = get_max_children(_matrix, row, column);
_matrix[column][row] = + row_max_children;
}
} if (!isHasNegtiveOne)
break;
} // Step: 4
int max = ;
for (int row = ; row < _matrix.size(); ++row)
{
std::sort(_matrix[row].begin(), _matrix[row].end(), std::greater<int>());
int current_max = _matrix[row][] + _matrix[row][];
if (max < current_max)
max = current_max;
} return _matrix.size() - max - ;
}// column as the parent, row as the child
// calculate how many nodes can row have
int
get_max_children(const vector<vector<int> > &_matrix, const int _row, const int _column)
{
int max_children = ; // count of negtive 2
const int count_n2 = std::count(_matrix[_row].begin(), _matrix[_row].end(), -);
const int count_not_n2 = _matrix.size() - count_n2; if ( >= count_not_n2)
{
// Step: 3.3
max_children = ;
}
else
{
// Step: 3.2
// Find the max 2 of _matrix[_row] which can not be _matrix[_row][_column]
vector<int> m_row = _matrix[_row];
m_row.erase(_column + m_row.begin());
std::sort(m_row.begin(), m_row.end(), std::greater<int>());
max_children = m_row[] + m_row[];
} return max_children;
}