# Cod sursa(job #311889)

Utilizator Data 4 mai 2009 17:32:09 Cc 100 cpp done Arhiva de probleme 2.17 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];

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;

/*
printf("%d\n", delta);

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

printf("%d\n", cuplaj);*/
}

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);