Nu aveti permisiuni pentru a descarca fisierul grader_test6.in
Cod sursa(job #544331)
Utilizator | Data | 1 martie 2011 14:20:37 | |
---|---|---|---|
Problema | Pixels | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.13 kb |
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
const char iname[] = "pixels.in";
const char oname[] = "pixels.out";
const int maxn = 105;
const int inf = 0x3f3f3f3f;
ifstream f(iname);
ofstream g(oname);
int S, D, A[maxn * maxn];
vector<pair<int, int> > E[maxn * maxn];
bool bfs() {
queue<int> Q;
Q.push(S);
memset(A, -1, sizeof(A));
A[S] = S;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
if (x == D)
continue;
for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
if (A[it -> x] == -1 && it -> y > 0)
A[it -> x] = x, Q.push(it -> x);//, fprintf(stderr, "(%d, %d, -> %d) ", x, it -> x, it -> y);
}
//fprintf(stderr, "d\n");
return (A[D] != -1);
}
pair<int, int> &muc(int x, int y) {
if (x == S || x == D)
return E[x][y];
for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
if (it -> x == y)
return *it;
}
int n, i, j, x, s, k, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int main() {
f >> n;
S = n * n;
D = n * n + 1;
for (i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
f >> x, E[S].push_back(make_pair(i * n + j, x)), s += x;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
f >> x, E[i * n + j].push_back(make_pair(D, x)), s += x,
E[D].push_back(make_pair(i * n + j, 0));
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
for (k = 0; k < 4; ++k) {
f >> x;
if (x == 0 || k > 1)
continue;
E[i * n + j].push_back(make_pair((i + dx[k]) * n + (j + dy[k]), x));
E[(i + dx[k]) * n + (j + dy[k])].push_back(make_pair(i * n + j, x));
}
while (bfs())
for (vector<pair<int, int> >::iterator it = E[D].begin(); it != E[D].end(); ++it) {
A[D] = it -> x;
int cost = inf;
for (i = D; i != S; i = A[i])
cost = min(cost, muc(A[i], i).y);// fprintf(stderr, "(%d, %d, -> %d) ", A[i], i, muc(A[i], i).y);
if (cost == 0)
continue;
for (i = D; i != S; i = A[i])
if (A[i] != S)
muc(A[i], i).y -= cost, muc(i, A[i]).y += cost;
else
muc(A[i], i).y -= cost;
s -= cost;
}
g << s << "\n";
}