Pagini recente » Cod sursa (job #2098722) | Cod sursa (job #393915) | Cod sursa (job #2525555) | Cod sursa (job #1950751) | Cod sursa (job #2982327)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define INF 0x3f3f3f3f
const int N = 205;
int n, x, y, flow, mflow;
int c[N][N], parent[N];
bool visited[N];
bool bfs()
{
queue<int> q;
memset(parent, 0, sizeof(parent));
memset(visited, false, sizeof(visited));
q.push(0);
visited[0] = true;
parent[0] = -1;
while(!q.empty()) {
int currentNode = q.front();
q.pop();
if (currentNode == 2*n+1)
return true;
for (int i=1;i<=2*n+1;i++){
if (!visited[i] && c[currentNode][i] > 0) {
q.push(i);
visited[i] = true;
parent[i] = currentNode;
}
}
}
return false;
}
void EdmondsKarp()
{
while(bfs()) {
for (int i=1;i<=n;i++) {
if (visited[n+i] && c[n+i][2*n+1] > 0) {
flow = INF;
parent[2*n+1] = n+i;
for (int node=2*n+1;node!=0;node=parent[node])
flow = min(flow, c[parent[node]][node]);
if (flow == 0)
continue;
for (int node=2*n+1;node!=0;node=parent[node]) {
c[parent[node]][node] -= flow;
c[node][parent[node]] += flow;
}
mflow += flow;
}
}
}
}
int main()
{
fin >> n;
for (int i=1;i<=n;i++){
fin >> x >> y;
c[0][i] = x;
c[i+n][2*n+1] = y;
for (int j=1;j<=n;j++){
if (i != j)
c[i][n+j] = 1;
}
}
EdmondsKarp();
fout << mflow << '\n';
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (c[i][n+j] == 0 && i != j){
fout << i << ' ' << j << '\n';
}
}
}
return 0;
}