Условие
Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.
Входные данные
На первой строке два числа $N$ $(N \le 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.
Выходные данные
Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.
Тесты
| Ввод | Вывод |
|
$5$ $5$ $1$ $2$ $3$ $2$ $2$ $4$ $3$ $5$ $2$ $5$ |
$1$ |
|
$5$ $5$ $1$ $3$ $3$ $5$ $5$ $2$ $2$ $4$ $4$ $1$ |
$2$ |
| $2$ $1$ $2$ $1$ |
$1$ |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <vector> using namespace std; const int MAXN = 500; int g[MAXN][MAXN]; int best_cost = 1000000000; void mincut(int n) { vector< int> v[MAXN]; for (int i = 0; i < n; ++i) v[i].assign (1, i); int w[MAXN]; bool exist [MAXN], in_a [MAXN]; for (auto &e :exist) e = true; for (int ph = 0; ph < n-1; ++ph) { for (auto &e: in_a) e = false; for (auto &e: w) e = 0; for (int it = 0, prev; it< n-ph; ++it) { int sel = -1; for (int i = 0; i < n; ++i) if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel])) sel = i; if (it == n-ph-1) { if (w[sel] < best_cost) best_cost = w[sel]; v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end()); for (int i=0; i<n; ++i) g[prev][i] = g[i][prev] += g[sel][i]; exist[sel] = false; } else { in_a[sel] = true; for (int i = 0; i < n; ++i) w[i] += g[sel][i]; prev = sel; } } } } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++){ int a,b; cin >> a >> b; a--; b--; g[a][b] = 1; g[b][a] = 1; } mincut (n); cout << best_cost; return 0; } |
Решение
Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.
Ссылки
Условие на e-olymp.com
Код на ideone.com