Задача
Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.
Входные данные
На первой строке два числа $N (N ≤ 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.
Выходные данные
Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 5 5 1 2 2 3 3 5 5 2 2 4 |
1 |
| 2 | 12 20 1 2 2 3 3 4 4 5 5 6 6 1 7 8 8 9 9 10 10 11 11 12 12 7 6 3 1 4 2 5 12 9 7 10 8 11 6 12 3 9 |
2 |
Код программы
|
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 |
#include <iostream> #include <vector> using namespace std; int n,m; vector<int> vis; bool dfs(int w0,int w,vector<vector<int>> &G) { vis[w0]=1; for (int q=1; q<=n; q++) { if (G[w0][q]>0 && vis[q]==0) { if (q==w || dfs(q,w,G)==0) { G[w0][q]--; G[q][w0]++; return 0; } } } return 1; } int main() { int u,v,i,k,res=10000000; scanf("%d %d\n",&n,&m); vector<vector<int>> G0(n+1,vector<int>(n+1,0)); for (i=0; i<m; i++) { scanf("%d %d\n",&u,&v); G0[u][v]=1; G0[v][u]=1; } for (i=2; i<=n; i++) { k=0; vector<vector<int>> G=G0; vis=vector<int>(n+1,0); while (!dfs(1,i,G)) { k++; vis=vector<int>(n+1,0); } if (k<res) res=k; } printf("%d",res); return 0; } |
Решение задачи
С помощью векторов будем запоминать связи между смешариками, где смешарики — это вершины. Две вершины будут смежными, если смешарики дружат между собой. Будем использовать обход в глубину. Для решения задачи воспользуемся алгоритмом Форда-Фалкерсона, чтобы найти максимальный поток. Будем искать максимальный поток от одной вершины до каждой. Из всех найденных максимальных потоков выбираем минимальный — это и будет ответом на задачу.
Вы так подробно описали построение графа, но обошли стороной, откуда куда мы будем пускать максимальный поток. А это намного интереснее.
Почему int dfs, когда Вы его используете как bool?
Спасибо, исправил.