Pagini recente » Monitorul de evaluare | Istoria paginii runda/primul | Cod sursa (job #996924) | Cod sursa (job #1780143) | Cod sursa (job #1790714)
#include <fstream>
#include <cstring>
using namespace std;
#include <queue>
#include <vector>
const int MAXN = 100;
const int MAXNODES = 2 * MAXN + 2;
const int INF = 5318008;
int seen[MAXNODES + 1], cap[MAXNODES + 1][MAXNODES + 1], flow[MAXNODES + 1][MAXNODES + 1], daddy[MAXNODES + 1];
vector <int> g[MAXNODES + 1];
queue <int> q;
int bfs(int n) {
memset(seen, 0, sizeof(seen));
int node;
seen[0] = 1;
q.push(0);
while (q.empty() == 0) {
node = q.front();
if (node != n)
for (int it : g[node])
if (seen[it] == 0 && flow[node][it] < cap[node][it]) {
seen[it] = 1;
daddy[it] = node;
q.push(it);
}
q.pop();
}
return seen[n];
}
inline int minim(int A, int B) {
if (A < B)
return A;
return B;
}
int maxflow(int n) {
int node, maxfl = 0, fl;
while (bfs(n)) {
for (auto it : g[n])
if (seen[it] && flow[it][n] < cap[it][n]) {
for (node = n, fl = INF, daddy[n] = it; node > 0; node = daddy[node])
fl = minim(fl, cap[daddy[node]][node] - flow[daddy[node]][node]);
for (node = n; node > 0; node = daddy[node]) {
flow[daddy[node]][node] += fl;
flow[node][daddy[node]] -= fl;
}
maxfl += fl;
}
}
return maxfl;
}
struct Node {
int gin, gout;
} v[MAXN + 1];
int main()
{
int n, i, s, d, j, maxfl;
ifstream fin("harta.in");
fin >> n;
for (i = 1; i <= n; ++i)
fin >> v[i].gin >> v[i].gout;
fin.close();
s = 0; d = 2 * n + 1;
for (i = 1; i <= n; ++i) {
g[s].push_back(i); g[i + n].push_back(d);
g[i].push_back(s); g[d].push_back(i + n);
cap[s][i] = v[i].gin; cap[i + n][d] = v[i].gout;
for (j = 1; j <= n; ++j)
if (i != j) {
cap[i][j + n] = 1;
g[i].push_back(j + n);
g[j + n].push_back(i);
}
}
maxfl = maxflow(d);
ofstream fout("harta.out");
fout << maxfl << '\n';
for (i = 1; i <= n; ++i)
for (j = n + 1; j <= 2 * n; ++j)
while (flow[i][j] > 0) {
fout << i << " " << j - n << '\n';
--flow[i][j];
}
fout.close();
return 0;
}