greedy hungarian algorithm

brute.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1000;

int n, graph[N][N], match[N];
bool visit[N];

bool find(int u) {
    if (visit[u]) {
        return false;
    }
    visit[u] = true;
    for (int v = 0; v < n; ++ v) {
        if (graph[u][v] && (match[v] == -1 || find(match[v]))) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            scanf("%d", graph[i] + j);
        }
    }
    for (int i = 0; i < n; ++ i) {
        match[i] = i;
    }
    do {
        bool valid = true;
        for (int i = 0; i < n; ++ i) {
            valid &= graph[i][match[i]];
        }
        if (valid) {
            for (int i = 0; i < n; ++ i) {
                printf("%d\n", match[i]);
            }
            return 0;
        }
    } while (std::next_permutation(match, match + n));
    puts("-1");
    return 0;
}

generator.rb

n = ARGV[0].to_i
puts n
puts [*1..n].map { [*1..n].map { rand(2) }.join(' ') }

hungary.cpp

#include <cstdio>
#include <cstring>

const int N = 1000;

int n, graph[N][N], match[N];
bool visit[N];

bool find(int u) {
    if (visit[u]) {
        return false;
    }
    visit[u] = true;
    for (int v = 0; v < n; ++ v) {
        if (graph[u][v] && (match[v] == -1 || find(match[v]))) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            scanf("%d", graph[i] + j);
        }
    }
    memset(match, -1, sizeof(match));
    for (int i = n - 1; i >= 0; -- i) {
        memset(visit, 0, sizeof(visit));
        if (!find(i)) {
            puts("-1");
            return 0;
        }
    }
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            if (match[j] == i) {
                printf("%d\n", j);
            }
        }
    }
    return 0;
}

input.txt

4
1 1 1 0
0 1 1 0
1 1 1 0
0 1 1 1

test.bash

#!/bin/bash
make brute
make hungary
while true; do
    if ruby gen.rb $@ > input.txt; then
        ./brute < input.txt > brute.out
        ./hungary < input.txt > hungary.out
        if diff brute.out hungary.out; then
            echo OK
        else
            echo WA
            break
        fi
    else
        break
    fi
done