Pagini recente » Cod sursa (job #808583) | Cod sursa (job #2232409) | Cod sursa (job #600015) | Cod sursa (job #2391017) | Cod sursa (job #2951992)
#include <bits/stdc++.h>
using namespace std;
const int VMAX = 1e2;
const int INF = 2e9;
const int NONE = -1;
struct MaxFlow {
int cap[1 + 2 * VMAX][1 + 2 * VMAX], flow[1 + 2 * VMAX][1 + 2 * VMAX];
bool visited[1 + 2 * VMAX]; int prev[1 + 2 * VMAX];
int V; int source, sink;
void add_edge (int a, int b, int c) {
cap[a][b] = c;
flow[a][b] = 0;
}
bool bfs () {
for (int node = 0; node <= 2 * V + 1; node ++) {
prev[node] = NONE;
visited[node] = false;
}
queue<int> q; q.push (source); visited[source] = true;
while (!q.empty ()) {
int node = q.front (); q.pop ();
for (int nxt = 1; nxt <= 2 * V + 1; nxt ++) {
if (!visited[nxt] && flow[node][nxt] < cap[node][nxt]) {
q.push (nxt); visited[nxt] = true; prev[nxt] = node;
if (nxt == sink)
return true;
}
}
}
return false;
}
int solve () {
int maxFlow = 0;
while (bfs ()) {
for (int node = V + 1; node <= 2 * V; node ++) {
if (visited[node] && flow[node][sink] < cap[node][sink]) {
prev[sink] = node;
int curr = sink, addFlow = INF;
while (curr != source) {
addFlow = min(addFlow, cap[prev[curr]][curr] - flow[prev[curr]][curr]);
curr = prev[curr];
}
curr = sink;
while (curr != source) {
flow[prev[curr]][curr] += addFlow;
flow[curr][prev[curr]] -= addFlow;
curr = prev[curr];
}
maxFlow += addFlow;
}
}
}
return maxFlow;
}
};
int main()
{
ifstream in ("harta.in");
ofstream out ("harta.out");
MaxFlow flow; in >> flow.V;
flow.source = 0, flow.sink = 2 * flow.V + 1;
for (int node = 1; node <= flow.V; node ++) {
int indeg, outdeg; in >> indeg >> outdeg;
flow.add_edge (flow.source, node, indeg);
flow.add_edge (node + flow.V, flow.sink, outdeg);
}
for (int first = 1; first <= flow.V; first ++)
for (int second = flow.V + 1; second <= 2 * flow.V; second ++)
if (first != second - flow.V)
flow.add_edge (first, second, 1);
flow.solve ();
vector<pair<int, int>> answer;
for (int first = 1; first <= flow.V; first ++)
for (int second = flow.V + 1; second <= 2 * flow.V; second ++)
if (flow.flow[first][second])
answer.push_back ({first, second - flow.V});
out << answer.size () << "\n";
for (pair<int, int> x : answer)
out << x.first << " " << x.second << "\n";
return 0;
}