Тема: timus 1109
Кто нибудь может выложить решение этой задачи с помощью алго Хопкрофта - Карпа? (Кун работает слишком долго хотя и укладывается по времени)
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » timus 1109
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Кто нибудь может выложить решение этой задачи с помощью алго Хопкрофта - Карпа? (Кун работает слишком долго хотя и укладывается по времени)
А оптимизацию с жадностью пробовал? По некоторым экспериментальным данным, с ней Кун даже быстрее Хопкрофта-Карпа
Обычный алгоритм с dfs нормально проходит...
#include <cstdio>
#include <vector>
using namespace std;
#define Size(x) (int)(x).size()
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define RepV(i,v) for (int i=0;i<Size(v);++i)
#define Fill(a,b) memset(&a,b,sizeof(a))
int n, m, v[1005], xy[1005], yx[1005];
vector<int> x[1005];
int go(int u){
if ( v[u]++ ) return 0;
RepV(i, x[u]) if ( !yx[x[u][i]] || go( yx[x[u][i]] ) ) {
xy[u] = x[u][i];
yx[x[u][i]] = u;
return 1;
}
return 0;
}
int main(){
int k;
scanf("%d%d%d", &n, &m, &k);
For(i, 1, k) {
int a, b;
scanf("%d%d", &a, &b);
x[a].push_back(b);
}
int max_bipartite_matching = 0;
For(i, 1, n) if ( !xy[i] ) {
Fill(v, 0);
max_bipartite_matching += go(i);
}
printf("%d", n + m - max_bipartite_matching );
return 0;
}
А что насчет реализации Хопркрофта - Карпа?
Ну а в чем проблема взять статью из википедии и написать по ней этого самого Хопкрофта-Карпа?
Я кстати тож не понимаю, нафиг он тут. Даже на Java нормально написанный Форд-Фалкерсон работает 0.125 для этой задачи.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » timus 1109