Условие

По легенде задачи, мы — хакеры, которые хотят запретить некому Bobnet’у общаться в своей внутренней сети. Сеть Bobnet разделена на несколько небольших сетей, в каждой подсети находится агент Bobnet, которому поручена передача информации путем перемещения от узла к узлу по каналам связи к шлюзам, ведущим в другие подсети.

То есть каждая сеть — граф, вершины которого олицетворяют узлы сети, некоторые из этих узлов — шлюзы, к которым пытается добраться агент Bobnet, а ребра — связи между узлами. По условию задачи, каждый шлюз может быть соединен максимум с двумя узлами, а так же мы можем разрывать связи между шлюзами и узлами (между двумя узлами — нет).

Чтобы решить задачу, надо разорвать все связи между шлюзами и узлами, чтобы агент Bobnet никак не смог выйти из своей подсети.

Входные данные

Инициализирующий ввод

Строка 1: 3 целых числа $N, L, E$

$N$ — общее количество узлов на уровне, включая шлюзы.
$L$ — количество связей на уровне.
$E$ — количество выходных шлюзов на уровне.

Следующие $L$ строк: 2 целых числа в каждой строке $(N_1, N_2)$, указывающие на связь между узлами с индексами $N_1$ и $N_2$ в сети.

Следующие $E$ строк: 1 целое число $EI$, обозначающее индекс узла-шлюза.

Входные данные для одного игрового хода

1 целое число $SI$, представляющее собой индекс узла, на котором в этот ход находится агент Bobnet.

Ожидаемый выход для одного игрового хода

Одна строка, состоящая из двух целых чисел $C_1$ и $C_2$, разделенных пробелом. $C_1$ и $C_2$ — это индексы узлов, между которыми вы хотите разорвать связь.

Ограничения
$2 \leqslant N \leqslant 500$
$1 \leqslant L \leqslant 1000$
$1 \leqslant E \leqslant 20$
$0 \leqslant N_1, N_2 < N$
$0 \leqslant SI < N$
$0 \leqslant C_1, C_2 < N$
Время ожидания одного хода $\leqslant 150$мс.

Код

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
  
using namespace std;

vector<vector<int>> g;
vector<int> d, u2, link_counters;
vector<bool> u1, m;
void bfs(int v) 

    queue<int> q;
    fill(m.begin(), m.end(), false);
    m[v] = true;
    int t = 0;
    q.push(v);
    while(!q.empty()) {
        for(int i=q.size(); i >= 1; --i) {
            int tmp = q.front();
            cerr << tmp << ' ';
            d[tmp] = t;
            for(auto e: g[tmp]) {
                if(u1[e] == false and m[e] == false) {
                    q.push(e);
                    m[e] = true;
                }
            }
            q.pop();
        }
        cerr << endl;
        ++t;
    }
}
  
int dfs(int v) {
    int tmp=0;
    for(int e: g[v]) {
        if(u1[e] == false and d[e] == (d[v] - 1))
            tmp = max(tmp, dfs(e));
    }
    tmp += link_counters[v];
    return tmp;
}
  
int main()
{
    // инициализация
    int n; // общее количество узлов на уровне, включая шлюзы
    int l; // количество связей на уровне
    int e; // количество выходных шлюзов на уровне
    cin >> n >> l >> e; cin.ignore();
    m.resize(n);
    d.resize(n);
    u1.resize(n, false);
    link_counters.resize(n, 0);
    g.resize(n, vector<int>());
    vector<int> values;
    vector<vector<int>> g2(n, vector<int>(n, 0));
    for (int i = 0; i < l; i++) {
        int n1; // определение связи между узлами N1 и N2
        int n2;
        cin >> n1 >> n2; cin.ignore();
        g[n1].push_back(n2);
        g[n2].push_back(n1);
    }
    for (int i = 0; i < e; i++) {
        int ei; // индекс шлюза
        cin >> ei; cin.ignore();
        u1[ei] = true;
        for(auto v: g[ei]) {
            link_counters[v]++;
            g2[v][ei] = g2[ei][v] = 1;
        }
    }
  
    // игровой цикл
    while (1) {
        int v=0;
        bool notNear=true;
        int si; // индекс узла, на котором в этот ход находится агент Bobnet
        cin >> si; cin.ignore();
        values=link_counters;
        for(auto e: g[si]) {
            if(u1[e] == true and g2[e][si] == 1 and g2[si][e] == 1) {
                notNear = false;
                g2[si][e] = g2[e][si] = 0;
                link_counters[si]--;
                cout << e << ' ' << si << endl;
            }
        }
        if(notNear) {
            bfs(si);
            for(int i=0; i < n; ++i) {
                if(link_counters[i] > 0) values[i] -= d[i];
                else values[i] = -1000;
            }
            for(int i=0; i < n; ++i) {
                if(link_counters[i] > 1) {
                    values[i] += dfs(i);
                }
            }
            for(int i=0; i < n; ++i) {
                if((values[v] < values[i]) or (values[v] == values[i] and d[i] < d[v])) v=i;
            }
            for(auto e: d) cerr << e << ' ';
            cerr << endl;
            for(auto e: link_counters) cerr << e << ' ';
            cerr << endl;
            for(auto e: values) cerr << e << ' ';
            // cerr << endl << v << endl;
            for(auto e: g[v]) {
                if(u1[e] == true and g2[e][v] == 1 and g2[v][e] == 1) {
                    g2[v][e] = g2[e][v] = 0;
                    link_counters[v]--;
                    cout << e << ' ' << v << endl;
                    break;
                }
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <iostream>

#include <string>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

vector<vector<int>> g;

vector<int> d, u2, link_counters;

vector<bool> u1, m;

void bfs(int v)

queue<int> q;

fill(m.begin(), m.end(), false);

m[v] = true;

int t = 0;

q.push(v);

while(!q.empty()) {

for(int i=q.size(); i >= 1; --i) {

int tmp = q.front();

cerr << tmp << ' ';

d[tmp] = t;

for(auto e: g[tmp]) {

if(u1[e] == false and m[e] == false) {

q.push(e);

m[e] = true;

}

q.pop();

}

cerr << endl;

++t;

}

int dfs(int v) {

int tmp=0;

for(int e: g[v]) {

if(u1[e] == false and d[e] == (d[v] - 1))

tmp = max(tmp, dfs(e));

}

tmp += link_counters[v];

return tmp;

}

int main()

{

// инициализация

int n; // общее количество узлов на уровне, включая шлюзы

int l; // количество связей на уровне

int e; // количество выходных шлюзов на уровне

cin >> n >> l >> e; cin.ignore();

m.resize(n);

d.resize(n);

u1.resize(n, false);

link_counters.resize(n, 0);

g.resize(n, vector<int>());

vector<int> values;

vector<vector<int>> g2(n, vector<int>(n, 0));

for (int i = 0; i < l; i++) {

int n1; // определение связи между узлами N1 и N2

int n2;

cin >> n1 >> n2; cin.ignore();

g[n1].push_back(n2);

g[n2].push_back(n1);

}

for (int i = 0; i < e; i++) {

int ei; // индекс шлюза

cin >> ei; cin.ignore();

u1[ei] = true;

for(auto v: g[ei]) {

link_counters[v]++;

g2[v][ei] = g2[ei][v] = 1;

}

// игровой цикл

while (1) {

int v=0;

bool notNear=true;

int si; // индекс узла, на котором в этот ход находится агент Bobnet

cin >> si; cin.ignore();

values=link_counters;

for(auto e: g[si]) {

if(u1[e] == true and g2[e][si] == 1 and g2[si][e] == 1) {

notNear = false;

g2[si][e] = g2[e][si] = 0;

link_counters[si]--;

cout << e << ' ' << si << endl;

}

if(notNear) {

bfs(si);

for(int i=0; i < n; ++i) {

if(link_counters[i] > 0) values[i] -= d[i];

else values[i] = -1000;

}

for(int i=0; i < n; ++i) {

if(link_counters[i] > 1) {

values[i] += dfs(i);

}

for(int i=0; i < n; ++i) {

if((values[v] < values[i]) or (values[v] == values[i] and d[i] < d[v])) v=i;

}

for(auto e: d) cerr << e << ' ';

cerr << endl;

for(auto e: link_counters) cerr << e << ' ';

cerr << endl;

for(auto e: values) cerr << e << ' ';

// cerr << endl << v << endl;

for(auto e: g[v]) {

if(u1[e] == true and g2[e][v] == 1 and g2[v][e] == 1) {

g2[v][e] = g2[e][v] = 0;

link_counters[v]--;

cout << e << ' ' << v << endl;

break;

}

Решение

Начнем с того, что если один узел связан с двумя шлюзами, нет никакой разницы, какую из его связей разрывать. Поэтому задача сводится к тому, чтобы определить узел, одну из связей со шлюзом которого надо разорвать. Для этого определим ценность разрыва связи в каждом узле.

Для начала, нужно посчитать количество связей, ведущих ко шлюзам, для каждого узла и записать эти значения в массив values, хранящий для каждого узла ценность разрыва связи в нем. После этого мы запускаем поиск в ширину из узла, в котором находится агент Bobnet, дабы определить расстояния от него до узлов, связанных со шлюзами. Чем узел дальше — тем менее важно разрывать в нем связь прямо сейчас, поэтому из ценности каждого узла вычитаем расстояние до него. Однако, это еще не все, ведь на графе с картинки снизу этот алгоритм бы разорвал связь в узле с единицей, вместо двойки и проиграл, ведь агент может пойти по зеленому пути, каждый узел которого связан с каким-то шлюзом, а узел, помеченный двойкой — с двумя, поэтому алгоритм бы не успел порвать все связи к концу пути.

Чтобы решить эту проблему, надо для каждого шлюза среди всех кратчайших путей от агента до него выбрать путь с максимальным количеством связанных со шлюзами узлов и добавить количество этих узлов к values. Тем самым, если вспомнить, что из ценности разрыва связи в каждом шлюзе мы вычитали расстояние до него, получится, что эта ценность равна разности между количеством связей узлов со шлюзами на пути и расстоянием до этого шлюза, то есть количество ходов, на которых можно игнорировать выбранный путь и не проиграть, только со знаком «минус».

Остается только каждый ход выводить номер шлюза, значение values для которого максимальное.