Условие

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.

Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать 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$

Код решения

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);
    }

}

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);

}

Решение

Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

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

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

В первой строке заданы количество вершин $n$ и ребер $m$ в графе соответственно $(1 \leq n \leq 100, 1 \leq m \leq 10000)$ . Каждая из следующих m строк содержит по два числа $u_i$ и $v_i$ $(1 \leq u_i, v_i \leq n);$ каждая такая строка означает, что в графе существует ребро между вершинами $u_i$ и $v_i$ .

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	5 4 1 2 5 3 4 5 3 4	NO
3	5 4 1 2 5 1 3 5 4 3	YES

Код программы

import java.util.*;
 
class Graph {
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        ArrayList<Integer> gr[] = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            gr[i] = new ArrayList<>();
        }
 
        int s = 0;
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            gr[u - 1].add(v - 1);
            gr[v - 1].add(u - 1);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        queue.push(s);
        boolean used[] = new boolean[n];
        used[s] = true;
 
        while (!queue.isEmpty()) {
            int v = queue.peek();
            queue.pop();
            for (int i = 0; i < gr[v].size(); ++i) {
                int to = gr[v].get(i);
                if (!used[to]) {
                    used[to] = true;
                    queue.push(to);
                }
            }
        }
        String answer = "YES";
        for (int i = 0; i < used.length; i++) {
            if (used[i] == false) {
                answer = "NO";
            }
        }
        System.out.println(answer);
    }
}

import java.util.*;

class Graph {

public static void main(String[] args) {

int n, m;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

m = scanner.nextInt();

ArrayList<Integer> gr[] = new ArrayList[n];

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

gr[i] = new ArrayList<>();

}

int s = 0;

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

int u, v;

u = scanner.nextInt();

v = scanner.nextInt();

gr[u - 1].add(v - 1);

gr[v - 1].add(u - 1);

}

LinkedList<Integer> queue = new LinkedList<>();

queue.push(s);

boolean used[] = new boolean[n];

used[s] = true;

while (!queue.isEmpty()) {

int v = queue.peek();

queue.pop();

for (int i = 0; i < gr[v].size(); ++i) {

int to = gr[v].get(i);

if (!used[to]) {

used[to] = true;

queue.push(to);

}

String answer = "YES";

for (int i = 0; i < used.length; i++) {

if (used[i] == false) {

answer = "NO";

}

System.out.println(answer);

}

Алгоритм

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

Ссылка на Ideone

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: связность

e-olymp 209. Защита от копирования

Условие

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

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

Тесты

Код решения

Решение

Ссылки

e-olymp 982. Связность