Условие
Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать 1 у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.
Входные данные
Hа первой строке два числа $N(N\leq 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.util.*; public class Main { static int maxn = 100; static int bestCost = Integer.MAX_VALUE; static int[][] relations = new int[Main.maxn][Main.maxn]; public static void mincut(int N) { Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>(); for (int i = 0; i < N; i++) { compressed_vertices.add(new Vector<Integer>()); compressed_vertices.get(i).add(i); } int[] weights; weights = new int[N]; boolean[] exist; exist = new boolean[N]; boolean[] in_A; in_A = new boolean[N]; for (int i = 0; i < N; i++) { exist[i] = true; } for (int ph = 0; ph < N - 1; ++ph) { for (int i = 0; i < N; i++) { in_A[i] = false; } for (int i = 0; i < N; i++) { weights[i] = 0; } int prev = 0; for (int it = 0; it < N - ph; ++it) { int sel = -1; for (int i = 0; i < N; ++i) { if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) { sel = i; } } if (it == N - ph - 1) { if (weights[sel] < bestCost) { bestCost = weights[sel]; } compressed_vertices.get(prev).addAll(compressed_vertices.get(sel)); for (int i = 0; i < N; ++i) { relations[prev][i] = relations[i][prev] += relations[sel][i]; } exist[sel] = false; } else { in_A[sel] = true; for (int i = 0; i < N; ++i) { weights[i] += relations[sel][i]; } prev = sel; } } } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int M = in.nextInt(); for (int i = 0; i < M; i++) { int U = in.nextInt() - 1; int V = in.nextInt() - 1; relations[U][V] = 1; relations[V][U] = 1; } mincut(N); System.out.print(bestCost); } } |
Решение
Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.