Pagini recente » Cod sursa (job #719520) | Cod sursa (job #48604) | Cod sursa (job #1829677) | Cod sursa (job #328429) | Cod sursa (job #2959032)
#include <fstream>
#include <queue>
#include <vector>
#include<climits>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
int BFS(int s, int N, vector<vector<int>> &adjList,
vector<vector<int>> &adjListIn, vector<vector<int>> &flux,
vector<vector<int>> &cost, vector<int> &tata) {
queue<int> queue;
vector<int> viz(N + 1, 0);
for (int i = 0; i <= N; i++) tata[i] = 0;
queue.push(s);
viz[s] = 1;
while (!queue.empty()) {
int x;
x = queue.front();
queue.pop();
for (auto it = adjList[x].begin(); it != adjList[x].end(); ++it) {
int y;
y = *it;
if (viz[y] == 0 && flux[x][y] < cost[x][y]) {
queue.push(y);
viz[y] = 1;
tata[y] = x;
if (y == N) return 1;
}
}
for (auto it = adjListIn[x].begin(); it != adjListIn[x].end(); ++it) {
int y;
y = *it;
if (viz[y] == 0 && flux[y][x] > 0) {
queue.push(y);
viz[y] = 1;
tata[y] = -x;
if (y == N) return 1;
}
}
}
return 0;
}
int maxFlow(int N, int s, int t, vector<vector<int>> &adjList,
vector<vector<int>> &adjListIn, vector<vector<int>> &flux,
vector<vector<int>> &cost) {
vector<int> tata(N + 1);
int fluxMax = 0;
while (BFS(s, N, adjList, adjListIn, flux, cost, tata)) {
// calculam i(P) = capacitatea reziduala minima pe un arc de pe drumul
// de adjList s adjList t determinat cu bf
int iP = INT_MAX; // i(P)
t = N;
while (t != s) {
if (tata[t] >= 0) { // arc direct - capacitate c(e)-flux(e)
if (cost[tata[t]][t] - flux[tata[t]][t] < iP)
iP = cost[tata[t]][t] - flux[tata[t]][t];
t = tata[t];
} else { // arc invers - capacitate flux(e)
if (flux[t][-tata[t]] < iP) iP = flux[t][-tata[t]];
t = -tata[t];
}
}
// revizuim fluxul de-a lungul lantului determinat
t = N;
while (t != s) {
if (tata[t] >= 0) { // arc direct - creste fluxul cu iP
flux[tata[t]][t] = flux[tata[t]][t] + iP;
t = tata[t];
} else { // arc invers - scade fluxul cu iP
flux[t][-tata[t]] = flux[t][-tata[t]] - iP;
t = -tata[t];
}
}
fluxMax += iP; // creste valoarea fluxului cu iP
}
return fluxMax;
}
int main() {
int n;
// creaza retea
in >> n;
int s = 2*n + 1;
int t = 2*n + 2;
int N = 2 * n + 2;
vector<vector<int>> adjList(N + 1);
vector<vector<int>> adjListIn(N + 1);
vector<vector<int>> flux(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> cost(N + 1, vector<int>(N + 1, 0));
for (int x = 1; x <= n; x++) {
adjList[s].push_back(x);
adjListIn[x].push_back(s);
}
for (int x = 1; x <= n; x++)
for (int y = n + 1; y <= 2 * n; y++) {
if (x != y - n) {
adjList[x].push_back(y);
adjListIn[y].push_back(x);
cost[x][y] = 1;
}
}
for (int y = n + 1; y <= 2 * n; y++) {
adjList[y].push_back(t);
adjListIn[t].push_back(y);
}
int sumaGrade = 0;
for (int i = 1; i <= n; i++) {
int d1, d2;
in >> d1 >> d2;
sumaGrade += d1;
cost[s][i] = d1;
cost[i + n][t] = d2;
}
int fluxMax = maxFlow(N, s, t, adjList, adjListIn, flux, cost);
if (fluxMax != sumaGrade) {
out << "Nu se poate construi un graf cu gradele date\n";
} else {
out << fluxMax << '\n';
for (int x = 1; x <= n; x++) {
for (auto it = adjList[x].begin(); it != adjList[x].end(); ++it) {
int y;
y = *it;
if (flux[x][y]) {
out << x << ' ' << y - n << '\n';
}
}
}
}
out.close();
in.close();
return 0;
}