В одной стране под названием Инфолэнд есть n городов, связанных между собой двусторонними дорогами. Цепью между городами a и b называется маршрут между этими городами, который использует каждую дорогу не более одного раза. Дороги в этой стране построены так, что для любых городов a и b существует ровно одна цепь, связывающая эти два города. Правительство этой страны приняло указ о контроле дорог своего государства. Было решено в некоторых городах создать комитеты по контролю всех дорог, начинающихся или заканчивающихся в этом городе. В целях экономии необходимо создать наименьшее возможное число таких комитетов, но чтобы любая дорога находилась под контролем хотя бы одного комитета. В ответ вывести минимальное число городов.
Мой алгоритм. Из условия очевидно,что данные города образуют граф,при этом этот граф будет деревом,тогда,чтобы найти минимальное количество городов необходимо найти его наименьшее вершинное покрытие. Вот тут и начинается проблема. Поиск наименьшего вершинного покрытия-это NP-полная задача. Но если бы это был двудольный граф,то задача сведётся к поиску максимального паросочетания. Вопрос: как мне свести мой граф к двудольному и вообще возможно ли такое? Можно ли считать мой алгоритм корректным? И если нет,то как тогда решить данную задачу Привожу код на С++,вылетает на большей части тестов,как исправить или написать лучше?
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<iomanip>
#include <set>
#pragma comment(linker, "/STACK:1677721600")
using namespace std;
int n;
vector <vector<int>> G1(n);
vector<vector<int>>K1(n);
vector<int>I(n);
int get_independent_set(int u)
{
if (I[u] != 0)
return I[u];
else
{
int children_sum = 0;
int grandchildren_sum = 0;
// цикл по всем детям
for (int i = 0; i < G1[u].size(); i++)
children_sum = children_sum + get_independent_set(G1[u][i]);
// цикл по всем внукам
for (int i = 0; i < K1[u].size(); i++)
grandchildren_sum = grandchildren_sum + get_independent_set(K1[u][i]);
// запоминаем, чтобы не пересчитывать ещё раз
I[u] = max(1 + grandchildren_sum, children_sum);
return I[u];
}
}
int main()
{
ifstream fin("input.txt");
ofstream fout("output.txt");
fin >> n;
vector <vector<int>> G(n);
vector<int>I1(n);
int i, v, k = 0;
while (fin >> i)
{
for (int j = 0; j < i; j++)
{
fin >> v;
G[k].push_back(v-1);
}
k++;
}
vector<bool>used(n);
queue<int>q1;
queue<int> q;
q.push(0);
vector<vector<int>>child(n);
vector<vector<int>>vnuki(n);
while (!q.empty())
{
int m = q.front();
q.pop();
used[m] = true;
for (int j = 0; j < G[m].size(); j++)
{
if (!(used[G[m][j]]))
{
child[m].push_back(G[m][j]);
q.push(G[m][j]);
for (int k = 0; k < G[G[m][j]].size(); k++)
{
if (G[G[m][j]][k] != m)
vnuki[m].push_back(G[G[m][j]][k]);
}
}
}
}
G1 = child;
K1 = vnuki;
I = I1;
int ver = get_independent_set(0);
fout << n - ver;
return 0;
}