Pagini recente » Cod sursa (job #1901439) | Cod sursa (job #473924) | Cod sursa (job #3282123) | Cod sursa (job #694097) | Cod sursa (job #2962147)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
vector<vector<int>> residualGraph;
vector<vector<int>> adjList;
vector<int> tt;
vector<int> viz;
int n, N;
bool bfs()
{
for(int i = 0; i <= N; ++i)
{
tt[i] = 0;
viz[i] = 0;
}
tt[0] = -1;
viz[0] = 1;
queue<int> q;
q.push(0);
while(!q.empty())
{
int crt = q.front();
q.pop();
for(int node : adjList[crt])
{
if(viz[node] == 0 && residualGraph[crt][node] > 0)
{
q.push(node);
viz[node] = 1;
tt[node] = crt;
if(node == N)
return true;
}
}
}
return false;
}
int getFlow()
{
int flow = INT_MAX;
int i = N;
while(i != 0)
{
flow = min(flow, residualGraph[tt[i]][i]);
i = tt[i];
}
return flow;
}
void updateResidual(int flow)
{
int i = N;
while(i != 0)
{
residualGraph[i][tt[i]] += flow;
residualGraph[tt[i]][i] -= flow;
i = tt[i];
}
}
int main()
{
fin>>n;
N = 2 * n + 1;
tt.resize(N + 1);
viz.resize(N + 1);
residualGraph.resize(N + 1, vector<int>(N + 1, 0));
adjList.resize(N + 1);
int x, y;
int res = 0;
for(int i = 1; i <= n; ++i)
{
fin>>x>>y;
residualGraph[0][i] = x;
residualGraph[i + n][N] = y;
adjList[0].push_back(i);
adjList[i].push_back(0);
adjList[i + n].push_back(N);
adjList[N].push_back(i + n);
}
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
if(i != j- n)
{
residualGraph[i][j]=1;
adjList[i].push_back(j);
adjList[j].push_back(i);
}
while(bfs())
{
int flow = getFlow();
res += flow;
updateResidual(flow);
}
fout<<res<<'\n';
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
if(residualGraph[j][i])
fout << i << " " << j - n << "\n";
return 0;
}