Pagini recente » Cod sursa (job #1422696) | Cod sursa (job #1020763) | Cod sursa (job #947507) | Cod sursa (job #225437) | Cod sursa (job #3188991)
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, capacitati[205][205];
vector<vector<int>> adj(205);
int bfs(int s,int d,vector<int> &parent)
{
fill(parent.begin(),parent.end(),-1);
queue<pair<int,int>> q;
q.push(pair(s,999999));
while(!q.empty())
{
int curr = q.front().first;
int flow = q.front().second;
q.pop();
for(int next : adj[curr])
{
if(parent[next] == -1 && capacitati[curr][next])
{
parent[next] = curr;
int new_flow = min(flow,capacitati[curr][next]);
if(next == d)
return new_flow;
q.push(pair(next,new_flow));
}
}
}
return 0;
}
int maxflow(int s,int d)
{
int flow = 0;
vector<int> parent(2*n+2);
int new_flow;
while(new_flow = bfs(s,d,parent))
{
flow += new_flow;
int curr = d;
while(curr != s)
{
int prev = parent[curr];
capacitati[prev][curr] -= new_flow;
capacitati[curr][prev] += new_flow;
curr = prev;
}
}
return flow;
}
int main()
{
fin>>n;
for(int i = 1;i<=n;i++)
{
fin>>capacitati[0][i]>>capacitati[n+i][2*n+1];
adj[0].emplace_back(i);
adj[i].emplace_back(0);
adj[n+i].emplace_back(2*n+1);
adj[2*n+1].emplace_back(n+i);
}
for(int i = 1;i<= n;i++)
for(int j = n+1;j<=2*n;j++)
if(i+n != j)
{
capacitati[i][j] = 1;
adj[i].emplace_back(j);
adj[j].emplace_back(i);
}
fout<<maxflow(0,2*n+1)<<endl;
for(int i = 1;i<= n;i++)
for(int j = n+1;j<=2*n;j++)
if(capacitati[i][j] == 0 && i+n != j)
fout<<i<<" "<<j-n<<endl;
return 0;
}