Cod sursa(job #311891)

Utilizator victorsbVictor Rusu victorsb Data 4 mai 2009 17:35:15
Problema Cc Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 105

int N, M;
int C[MAX_N][MAX_N];
vector<int> G[MAX_N];
bool viz[2 * MAX_N];
int dest[MAX_N];
int P[MAX_N];
int Y[2 * MAX_N];

void read() {
    scanf("%d", &N);
    M = N;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            G[i].push_back(j);

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            scanf("%d", &C[i][j]);
}

int cupleaza(int nod) {
    vector<int>::iterator it;
    
    viz[nod] = true;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
        if (Y[nod] + Y[N + *it] == C[nod][*it] && dest[*it] != nod) {
            viz[N + *it] = 1;
            if (dest[*it] == 0 || (!viz[dest[*it]] && cupleaza(dest[*it]))) {
                P[nod] = *it;
                dest[*it] = nod;
                return 1;
            }
        }

    return 0;
}

void solve() {
    int cuplaj = 0, delta;

    while (1) {
        int ok = 0;
        while (!ok) {
            ok = 1;
            memset(viz, 0, sizeof(viz));
            for (int i = 1; i <= N; ++i)
                if (!P[i] && cupleaza(i))
                    ++cuplaj, ok = 0;
        }
        if (cuplaj == N) break;
        
        delta = 1 << 30;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                if (viz[i] && !viz[N + j])
                    delta = min(delta, C[i][j] - Y[i] - Y[N + j]);

        for (int i = 1; i <= N; ++i)
            Y[i] += viz[i] * delta;
        for (int i = 1; i <= M; ++i)
            Y[N + i] -= viz[N + i] * delta;
    }

    int sol = 0;
    for (int i = 1; i <= N + M; ++i)
            sol += Y[i];
    printf("%d\n", sol);
}

int main() {
    freopen("cc.in", "r", stdin);
    freopen("cc.out", "w", stdout);

    read();
    solve();

    return 0;
}