Тема: timus 1109

Кто нибудь может выложить решение этой задачи  с помощью алго Хопкрофта - Карпа? (Кун работает слишком долго хотя и укладывается по времени)

2

Re: timus 1109

А оптимизацию с жадностью пробовал? По некоторым экспериментальным данным, с ней Кун даже быстрее Хопкрофта-Карпа

3

Re: timus 1109

Обычный алгоритм с 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;
}

Re: timus 1109

А что насчет реализации Хопркрофта - Карпа?

5

Re: timus 1109

Ну а в чем проблема взять статью из википедии и написать по ней этого самого Хопкрофта-Карпа?
Я кстати тож не понимаю, нафиг он тут. Даже на Java нормально написанный Форд-Фалкерсон работает 0.125 для этой задачи.

Джеймс Гослинг с нами!