VPF::задача на максимальное паросочетание

Stolzen

Дата 27.2.2011, 13:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Доброе время суток!

Я вот нашел одну задачу
http://acm.mipt.ru/judge/problems.pl?problem=010

Но почему-то алгоритм Куна на ней отказывается работать - пробовал различные вариации, и всегда на 5-м тесте ошибка. В чем может быть дело?

Например, если взять алгоритм отсюда http://e-maxx.ru/algo/kuhn_matching

Код


#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;

vector<vector<int> > g;
vector<int> mt;

vector<char> used;

bool try_kuhn_dfs(int v) {
    if (used[v])  return false;
    used[v] = true;
    for (size_t i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (mt[to] == -1 || try_kuhn_dfs (mt[to])) {
            mt[to] = v;

            return true;
        }
    }

    return false;
}


#define in cin

int main() {
    //ifstream in("input.txt");
    in >> n >> k;

    g.resize(n);

    int c, a, b;
    in >> c;

    for (int i = 0; i < c; ++i) {
        in >> a >> b;
        g[a - 1].push_back(b - 1);
    }

    mt.resize(k);
    mt.assign(k, -1);

    for (int v = 0; v < n; ++v) {
            used.assign(n, false);
            try_kuhn_dfs(v);
    }


    vector<pair<int, int> > the_answer;
    the_answer.reserve(k);

    for (int v = 0; v < k; ++v) {
        if (-1 != mt[v]) {
            the_answer.push_back(make_pair(v + 1, mt[v] + 1));
        }
    }

    sort(the_answer.begin(), the_answer.end());

    cout << the_answer.size() << endl;

    for (size_t i = 0; i < the_answer.size(); ++i) {
        cout << the_answer[i].first << ' ' << the_answer[i].second << endl;
    }

    return 0;
}

Ломается на 5-м тесте.

И еще - может быть, кто-нибудь подскажет другую реализацию этого алгоритма? И, если кто-то знает, какую-нибудь задачу на поиск максимального парасочетания в двудольном графе, с контестером, чтобы можно было проверить правильность алгоритма.

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Stolzen

Дата 27.2.2011, 13:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

С проверкой

Код


    if (0 == n || k == 0) {
        cout << 0 << endl;
        return 0;
    }

Код


    if (0 == c) {
        cout << 0 << endl;
        return 0;
    }

Тоже ошибка на 5-м тесте.

Более того, нашел алгоритм Хопкрофта-Карпа, попробовал его - тоже самое.

Код


#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;

const int MAXN1 = 50000;
const int MAXN2 = 50000;
const int MAXM = 150000;

int n1, n2, edges, last[MAXN1], prev[MAXM], head[MAXM];
int matching[MAXN2], dist[MAXN1], Q[MAXN1];
bool used[MAXN1], vis[MAXN1];

void init(int _n1, int _n2) {
    n1 = _n1;
    n2 = _n2;
    edges = 0;
    fill(last, last + n1, -1);
}

void addEdge(int u, int v) {
    head[edges] = v;
    prev[edges] = last[u];
    last[u] = edges++;
}

void bfs() {
    fill(dist, dist + n1, -1);
    int sizeQ = 0;
    for (int u = 0; u < n1; ++u) {
        if (!used[u]) {
            Q[sizeQ++] = u;
            dist[u] = 0;
        }
    }
    for (int i = 0; i < sizeQ; i++) {
        int u1 = Q[i];
        for (int e = last[u1]; e >= 0; e = prev[e]) {
            int u2 = matching[head[e]];
            if (u2 >= 0 && dist[u2] < 0) {
                dist[u2] = dist[u1] + 1;
                Q[sizeQ++] = u2;
            }
        }
    }
}

bool dfs(int u1) {
    vis[u1] = true;
    for (int e = last[u1]; e >= 0; e = prev[e]) {
        int v = head[e];
        int u2 = matching[v];
        if (u2 < 0 || (!vis[u2] && (dist[u2] == dist[u1] + 1) && dfs(u2))) {
            matching[v] = u1;
            used[u1] = true;
            return true;
        }
    }
    return false;
}

int maxMatching() {
    fill(used, used + n1, false);
    fill(matching, matching + n2, -1);
    for (int res = 0;;) {
        bfs();
        fill(vis, vis + n1, false);
        int f = 0;
        for (int u = 0; u < n1; ++u)
            if (!used[u] && dfs(u))
                ++f;
        if (!f)
            return res;
        res += f;
    }
}

#define in cin

int main() {
    //ifstream in("input.txt");
    int n, k;
    in >> n >> k;

    if (0 == n || k == 0) {
        cout << 0 << endl;
        return 0;
    }

    init(n, k);

    int c, a, b;
    in >> c;

    if (0 == c) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < c; ++i) {
        in >> a >> b;
        addEdge(a - 1, b - 1);
    }

    cout << maxMatching() << endl;

    for (int i = 0; i < n2; ++i) {
        if (matching[i] != -1) {
            cout << i + 1 << ' ' << matching[i] + 1 << endl;
        }
    }

    return 0;
}

Где ж собака порылась? Никак не могу понять.

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Stolzen

Дата 27.2.2011, 16:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Решил не очень ясным способом - взял другую долю и решал для нее (граф ведь двудольный, раньше я решал для доли с открытками, теперь для доли с конвертами)

Код


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    BufferedReader in;
    PrintWriter out;

    StreamTokenizer st;

    int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    private int m, n;
    
    int[][] g;
    int[] c;
    
    private boolean[] used;
    private int[] mt;
    
    private boolean bipart(int v) {
        if (used[v]) {
            return false;
        }
        
        used[v] = true;
        
        for (int i = 0; i < c[v]; i++) {
            int to = g[v][i];
            
            if (mt[to] == -1 || bipart(mt[to])) {
                mt[to] = v;
                
                return true;
            }
        }
        
        return false;
    }

    void solve() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        
        st = new StreamTokenizer(in);
        
        m = nextInt();
        n = nextInt();
        
        int k = nextInt();
        
        g = new int[n][(m + n)];
        c = new int[n];
        
        for (int i = 0; i < k; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            
            g[v][c[v]] = u;
            c[v]++;
        }

        mt = new int[m];
        used = new boolean[n];
        
        Arrays.fill(mt, -1);
        
        
        for (int v = 0; v < n; v++) {
            Arrays.fill(used, false);
            bipart(v);
        }
        
        StringBuilder sb = new StringBuilder(512);
        
        int result = 0;
        for (int i = 0; i < m; i++) {
            if (mt[i] != -1) {
                result++;
                sb.append(i + 1).append(' ').append(mt[i] + 1);
                sb.append('\n');
            }
        }
        
        out.println(result);
        out.println(sb);

        

        out.close();
        
        System.exit(0);
    }

    public static void main(String[] args) throws IOException {
        (new Main()).solve();
    }
}

Но почему это прошло, а то - нет, я так и не понял.

Это сообщение отредактировал(а) Stolzen - 27.2.2011, 16:29

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Интересные и занимательные задачи по программированию \| Следующая тема »